Many problems that are hard to solve share a curious feature: if someone proposes a solution, checking it is easy. Finding a route that visits every city exactly once may require an enormous search; verifying that a given route does so only requires walking through it. The class NP captures exactly this idea. It is often misunderstood, starting with its name: NP does not stand for "non-polynomial".
First definition: verifiers
A verifier for a language A is an algorithm V that takes two inputs: an instance w and an extra string c, called a certificate (or witness). It must hold that:
w ∈ A if and only if there is a certificate c such that V accepts ⟨w, c⟩
The verifier is polynomial if its running time is polynomial in the length of w. Consequently a useful certificate must also have polynomial length, because V would not have time to read a longer one.
NP is the class of languages that have a polynomial verifier.
The key point is the asymmetry:
- if w ∈ A, a certificate that convinces the verifier exists;
- if w ∉ A, no certificate convinces it.
We are not asked to find the certificate, only that it exists and can be checked quickly.
Second definition: nondeterministic machines
A nondeterministic Turing machine decides a language in time t(n) if every computation branch halts within t(n) steps and the machine accepts when at least one branch accepts.
NP is the class of languages decided by a nondeterministic machine in polynomial time. Hence the name: Nondeterministic Polynomial time.
The two definitions are equivalent:
- from verifier to nondeterministic machine: the machine "guesses" the certificate, writing one symbol per branch, then runs the verifier;
- from nondeterministic machine to verifier: the certificate is the sequence of choices leading to an accepting branch, and the verifier simulates the machine following those choices.
Examples of certificates
| Problem | Instance | Certificate | Check |
|---|---|---|---|
| SAT | Boolean formula | Truth assignment to the variables | Evaluate the formula |
| Hamiltonian path | Graph, nodes s and t | Sequence of nodes | Each node appears once, edges exist |
| Clique | Graph, integer k | Set of k nodes | Every pair is connected |
| Subset sum | Numbers and target T | Subset of the numbers | The sum is T |
| Composite numbers | Integer N | A divisor d with 1 < d < N | Divide N by d |
| 3-colourability | Graph | Colour of each node | Edge endpoints have different colours |
In every case verification is clearly polynomial, while naive search tries an exponential number of candidates: 2ⁿ assignments, n! orderings, 2ⁿ subsets, 3ⁿ colourings.
Where NP sits among other classes
These inclusions hold:
P ⊆ NP ⊆ EXPTIME
- P ⊆ NP: if a problem is solvable in polynomial time, the verifier can ignore the certificate and solve it directly.
- NP ⊆ EXPTIME: a polynomial verifier turns into a deterministic algorithm by trying every possible certificate, of which there are at most exponentially many.
We know that P ≠ EXPTIME, thanks to the time hierarchy theorem. So at least one of the two inclusions is strict, but we do not know which. If P = NP, the second would be strict; if NP = EXPTIME, the first.
The asymmetry between yes and no
The definition of NP treats positive and negative answers differently. To show that a formula is satisfiable, one assignment is enough. To show that it is not, no short certificate is known: in general we must be convinced that none of the 2ⁿ assignments works.
The class of complements of NP problems is called coNP. It is conjectured that NP ≠ coNP, but this too is open. Some problems lie in both: for instance primality, which is in P, and factoring in its decision version.
Common misconceptions
- "NP means non-polynomial": false. Every problem in P is also in NP.
- "NP problems are the hard ones": imprecise. The hardest problems in NP are the NP-complete ones; NP also contains easy problems.
- "An NP problem needs exponential time": we do not know that. If P = NP, every problem in NP would have a polynomial algorithm.
- "Optimization problems are in NP": NP contains decision problems, with a yes or no answer. Optimization versions are linked to decision ones by adding a threshold: "is there a route of length at most k?".
In short
- NP is the class of problems whose positive answers have certificates checkable in polynomial time.
- Equivalently, it is the class of problems decided by a nondeterministic machine in polynomial time.
- SAT, Hamiltonian path, clique, subset sum and 3-colourability are typical examples.
- P ⊆ NP ⊆ EXPTIME holds, and at least one inclusion is strict.
- Negative answers generally lack short certificates: hence the class coNP.
