The Classes P and NP

Polynomial-time deciding, polynomial-time verifying, and the open question between them.

The idea

P and NP are the central classes of complexity theory, which asks not what can be decided at all but what can be decided quickly, with time measured as a function of the input length $n$.

P is the class of languages that some deterministic Turing machine decides in time $O(n^{k})$ for a fixed $k$. Any fixed power qualifies, and constants and lower-order terms are ignored, which makes the class robust under reasonable changes of machine model. It is the standard formalization of tractable.

NP is the class of languages whose yes-instances can be checked quickly, even when finding the answer is hard. Precisely, $L$ is in NP when there is a polynomial-time verifier $V$ and a polynomial $p$ such that $w \in L$ if and only if some certificate $c$ with $|c| \le p(|w|)$ makes $V(w, c)$ accept. A nondeterministic polynomial-time machine yields the same class — guessing the certificate is the nondeterminism, checking it is the polynomial work — and the N stands for nondeterministic, not for non-polynomial.

The definition is one-sided: it promises a short certificate for strings in $L$ and nothing for strings outside it. A Hamiltonian path is its own certificate that a graph has one; no comparably short certificate that a graph has no Hamiltonian path is known.

$\mathrm{P} \subseteq \mathrm{NP}$, since a verifier may ignore the certificate and decide the instance itself. Whether the containment is strict — whether checking a solution really is easier than finding one — is the P versus NP question, and it is open.

Ways to work on it

• Walkthrough. Verifiers, certificates, polynomial time, and why P ⊆ NP.
• Practice. Read off the certificate or polynomial bound that places a problem in P or NP.
• Hardest. Bound a verifier and justify NP membership from the definition.

Not sure where to start? Take the ten-question placement test.