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\}^*$ — 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 \iff \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:

$$\textbf{Is } P = NP\,?$$

Most computer scientists believe $P \neq 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(\langle G\rangle, 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.