Introduction To NP-Completeness

Different types of problems are discussed in this tutorial, some of the problems are easy and some problems are hard to solve. So, what makes the problems easy or hard? Hence, this is the main question of complexity theory.

---

In computer science, some problems are solvable, and also there exist some problems which are not solvable by computers.

The problems, which are solvable, may be solved by an algorithm in polynomial time or may not be solved by any algorithm in polynomial time.

In this context, the problems are categorized into different classes.

The computational problems are divided into three main classes:

1. Polynomial problems (P)
2. Exponential problems (E)
3. Intractable (non-computable) problems (I)

---

Polynomial problems (P)

A problem belongs to P-Class, if there exists an algorithm that solves the problem in time T(n)=O(n^c), where c is a constant.

The problems of this class are easy problems. Some problems are listed below.

---

Examples

1. Sorting: the algorithms used for sorting run in O(n log n) or in O(n^2) time.
2. All-pairs shortest path: this algorithm runs in O(n^3) time.
3. Minimum spanning tree: the algorithm runs in O(E log E) time, which is less than O(E^2).

---

Exponential problems (E)

If a polynomial-time algorithm does not exist to solve a problem, but the problem can be solved in O(n^u(n)) time, where u(n) increases rapidly with the increase of n.

There are many problems that are solved in exponential time, but the polynomial-time algorithm is not known to solve them. And moreover, we don't know whether they can be solved in polynomial time or not.

---

Definition of NP

Definition-I	A problem belongs to Non-deterministically Polynomial (NP) class, it can be solved in a polynomial number of nondeterministic moves using a nondeterministic Turing machine
Definition-II	A problem belongs to NP-class if the solution of the problem comes from a finite set of possibilities, and the correctness of a candidate solution can be verified in polynomial time.

Thus NP is the class of all non-deterministically polynomial problems. Hence, P is a subset of NP.

---

Happy Exploring!