NP-Completeness

NP-completeness is a property of some computational problems, which makes them amongst the hardest problems, and at
least as hard as each other.

Definition

A decision problem is a problem with a yes/no answer (or 0/1, true/false).

Polynomial time is a running time for an algorithm which is some polynomial multiplied by the size of the algorithm’s
inputs \(N\), such as \(N\), \(log\ N\), \(N\ log\ N\), \(N^2\), or \(N^3\), but not \(2^N\) or \(N!\).

A deterministic algorithm is one which, when it has to pursue several options, needs to pursue them one at a time.
A nondeterministic algorithm is one which, when it has to pursue several options, can pursue them simultaneously.
A nondeterministic algorithm is faster than a deterministic algorithm, but it is no more powerful in the sense of
being able to solve problems that a deterministic algorithm can’t.

The class \(P\) is the class of decision problems that can be solved in polynomial time by a deterministic algorithm.
The class \(NP\) is the class of decision problems that can be solved in polynomial time by a nondeterministic algorithm.
It follows from this that \(P\) is a subset of \(NP\).

A polynomial reduction is an polynomial time algorithm that can transform an instance of a problem A
(decision or otherwise) into an instance of another problem B, such that the solution is preserved, i.e., for every
instance of A, if the solution of A is yes, then the instance of B produced by the polynomial transformation will also
be yes, and the same for false, or any other value.

A problem (decision or otherwise) is \(NP{\text-}hard\) if every problem in \(NP\) can be reduced to it by a polynomial reduction.
So \(NP{\text-}hard\) can be read as “at least as hard as \(NP\)“.
A problem is \(NP{\text-}complete\) if it is \(NP{\text-}hard\) and it is in \(NP\).

So a problem is \(NP{\text-}hard\) but not \(NP{\text-}complete\) if it isn’t in \(NP\).
There are two two reasons for this:
1. It isn’t a decision problem, which means it isn’t in \(NP\)
2. It isn’t decidable, e.g., the Turing machine Halting Problem is \(NP{\text-}hard\), but not in \(NP\) because the definition of \(NP\)
requires there is an algorithm, but by definition no algorithm exists for undecidable problems

Since every problem in \(NP\) can be reduced to any \(NP{\text-}complete\) problem, but the converse is not true, the \(NP{\text-}complete\)
problems can be seen as the hardest problems in \(NP\).

Most scientists believe that there is no polynomial time algorithm that can solve an \(NP{\text-}hard\) problem.
This means that there are problems in \(NP\) that are not in \(P\), so \(P\) is not equal to \(NP\).
This is the \(P{\text-}NP\ Problem\).