P, NP, and verification

Two kinds of "easy"

Every algorithm so far in this course ran in polynomial time — $O(n^k)$ for some constant $k$. We call such problems tractable, and the class of all of them is P. Formally, a decision problem (one with a yes/no answer) is a language $L\subseteq \{0,1{\}}^{\ast }$ — the set of input encodings whose answer is "yes". Then

$$P=\{L:\text{some algorithm decides }L\text{ in }O(n^k)\text{ time}\}.$$

NP captures a weaker notion of easy: not "can you solve it fast?" but "can you check a proposed answer fast?" The proposed answer is called a certificate $y$. A problem is in NP if there is a polynomial-time verification algorithm $A(x,y)$ such that

$$x\in L⟺\exists y,|y|=O(|x{|}^c),A(x,y)=1.$$

Read it carefully: $x$ is a yes-instance iff some polynomial-length certificate $y$ makes the verifier accept. The certificate must be short (polynomial in $|x|$) — an exponential-length "proof" would not help, because you could not even read it in polynomial time. NP stands for nondeterministic polynomial: a hypothetical machine that could "guess" the right $y$ and then verify it would run in polynomial time.

Why P ⊆ NP

Every problem you can solve fast you can also verify fast: ignore the certificate entirely and just re-solve from scratch. So a poly-time decider for $L$ is already a poly-time verifier (with an empty or ignored certificate), giving $P\subseteq NP$. The trillion-dollar open question is whether the containment is strict:

$$\text{Is }P=NP?$$

Most computer scientists believe $P\ne NP$ — for thousands of NP problems we can verify a solution in a heartbeat but finding one seems to require exhausting exponentially many candidates. It has been open since Cook's 1971 paper and carries a \$1{,}000{,}000 Clay Millennium Prize. Nobody has proved it either way.

Worked example — two certificates

HAM-CYCLE asks: does graph $G$ have a Hamiltonian cycle (a simple cycle visiting every vertex exactly once)? Finding one seems to need trying up to $(n-1)!$ orderings. But checking is trivial:

• Certificate $y$: a sequence of the $|V|$ vertices, claimed to be the cycle.
• Verifier $A(⟨G⟩,y)$: confirm $y$ lists every vertex exactly once, and that each consecutive pair (and the wrap-around) is an edge of $G$. That is $O(n^2)$ — clearly polynomial.

So HAM-CYCLE $\in$ NP even though no polynomial solver is known.

3-CNF-SAT asks: is a boolean formula in 3-conjunctive-normal-form (an AND of clauses, each an OR of exactly 3 literals) satisfiable? For $n$ variables there are $2^n$ assignments to search.

• Certificate $y$: a truth assignment to all variables, e.g. $x_1=1,x_2=0,x_3=1,\dots$
• Verifier: plug $y$ into the formula and evaluate. Linear in the formula length.

Again, easy to check, seemingly hard to find — the signature of an NP problem.

Optimization vs. decision

NP-completeness theory is stated for decision problems, but real problems are usually optimization problems (find the shortest path, the largest clique). The trick: an optimization problem is no easier than its decision version. SHORTEST-PATH (find the shortest path) has a decision cousin PATH (is there a path of $\le k$ edges?). If you could solve the optimization version fast, you could answer the decision version fast (just compare the optimum to $k$). So proving the decision problem hard proves the optimization problem at least as hard — which is exactly the direction we want.