# 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$$.