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\).