P versus NP: Whether Finding Is as Easy as Checking — Epoche C1
The P versus NP problem asks whether every search problem whose proposed answers can be checked quickly can also be solved quickly. That is a narrower question than the one usually reported, which is whether there exist problems computers cannot solve quickly, and the narrower question is the interesting one because the broader question was answered in 1965 and the answer is yes. Separating the two is the first task of this essay. The second is to show why a single theorem from 1971 concentrates the whole matter into one problem about logical formulas, and the third is to set out what a proof would have to look like, given three theorems that each rule out a family of methods. What was already settled, and by what argument Complexity theory studies decision problems. A decision problem, or language $L$, is a set of finite strings, and to solve it is to decide, for an input $x$ of length $n$, whether $x$ belongs to $L$. Write $\mathrm{DTIME}(f(n))$ for the class of languages decidable by a deterministic Turing machine — the standard idealised computer, a finite control moving a read-write head over an unbounded tape — within $f(n)$ steps on inputs of length $n$. Hartmanis and Stearns (1965) proved that more time buys more computational power. Their time hierarchy theorem states that if $f$ is well behaved, in the sense that a machine can compute $f(n)$ from $n$ within roughly $f(n)$ steps, then $\mathrm{DTIME}(f(n))$ is a proper subset of $\mathrm{DTIME}(f(n)\log f(n))$. The proof is a diagonalisation, the same manoeuvre by which Cantor showed the reals uncountable, transposed to machines. Build a machine $D$ that, given the encoding $\langle M\rangle$ of a machine as its input, simulates $M$ running on $\langle M\rangle$ for $f(n)$ steps and then outputs the opposite of whatever $M$ output. No machine running within $f(n)$ steps can decide the language of $D$, because such a machine would have to disagree with itself on its own encoding. The extra $\log f(n)$ factor is not decorative: it is the overhead a universal simulator pays to keep track of which machine it is imitating and how many steps remain, and it is the reason the theorem separates $f(n)$ from $f(n)\log f(n)$ rather than from $f(n)$ itself. The consequence is that problems solvable in exponential time but provably not in polynomial time exist. So the existence of intractable problems is not at issue. What the theorem cannot do is locate any particular natural problem on either side of the line, and that is where P versus NP begins. The asymmetry between solving and checking The class $\mathrm{P}$ contains the languages decidable in time $O(n^k)$ for some fixed constant $k$. Polynomial time is the accepted formalisation of "efficiently solvable" for two reasons that are worth separating. Polynomials are closed under composition and addition, so an efficient procedure that calls another efficient procedure a polynomial number of times remains efficient — which means the class is stable under the ordinary way of building algorithms out of subroutines. And the class is the same whichever reasonable machine model is used, since the standard models simulate one another with polynomial overhead; a definition tied to linear or quadratic time would not survive the change of model. The class $\mathrm{NP}$ is defined by a different question, and this is exactly the point the popular summary loses. It is defined not by how hard a problem is to solve but by how easy a proposed solution is to check. A language $L$ is in $\mathrm{NP}$ if there exist a polynomial-time algorithm $V$, called a verifier , which reads the input together with a proposed solution $w$ called a certificate , and a polynomial $p$ bounding the certificate's length, such that $$x \in L \iff \text{there exists } w \text{ with } |w| \le p(|x|) \text{ and } V(x, w) = 1.$$ The letter N stands for "nondeterministic", from the equivalent original definition in terms of a machine allowed to branch into several successor states at each step and to accept if any branch accepts. The two definitions match because a branching machine's sequence of choices is itself a string of polynomial length, and a verifier can be given that string as its certificate and follow the choices deterministically. The verifier formulation is the more useful one here, because it displays the asymmetry the problem is about. Boolean satisfiability, SAT, is the standard example and the one everything below turns on. The input is a logical formula built from variables, each of which may be set true or false, using conjunction, disjunction and negation; the question is whether some assignment of truth values makes the whole formula true. Checking a proposed assignment is easy: substitute and evaluate, in time proportional to the length of the formula. Finding one looks entirely different. A formula with 100 variables admits $2^{100} \approx 1.27\times10^{30}$ assignments. At $10^{9}$ evaluations per second, exhausting them takes about $1.27\times10^{21}$ seconds; a year is roughly $3.16\times10^{7}$ seconds, so the search takes about $4\times10^{13}$ years, some three thousand times the age of the universe. That calculation, however, establishes only that one particular method is hopeless, and it is worth being explicit that it proves nothing about the problem. Two facts show why. Every problem in $\mathrm{NP}$ can be decided by trying all certificates, of which there are at most $2^{p(n)}$, each checked in polynomial time; so $\mathrm{NP}$ sits inside exponential time, and by the hierarchy theorem exponential time strictly exceeds $\mathrm{P}$. Both containments are known; what is unknown is where $\mathrm{NP}$ falls between them. And in practice, as Fortnow (2009) records, SAT solvers routinely dispose of industrial formulas with hundreds of thousands of variables, while their worst-case running times remain exponential. The question is whether the gap between checking and finding is a fact about the pr