The True Challenge of P vs. NP Lies in Proof Limitations — Epoche C1
The question, and what would count as an answer The P versus NP problem asks whether every yes-or-no question whose affirmative answers can be checked quickly can also be answered quickly from scratch. It is one of the seven Millennium Prize Problems announced by the Clay Mathematics Institute in 2000, and the reason usually given for its remaining open is that the problems at its centre are too hard: the search spaces are astronomical, so no fast algorithm can exist, and the proof awaits ingenuity. That locates the obstacle in the wrong place. What blocks a proof is not a shortage of hard problems; it is that each of the three families of technique complexity theory actually possesses has been shown — by a theorem, not by a shrug — to be incapable of settling the question. The difficulty concerns the reach of our proofs rather than the hardness of our problems. The argument turns on a single quantifier, so the terms must be exact. A decision problem is a set of finite strings; solving it means, given a string $x$ of length $n$, deciding whether $x$ belongs to the set. The class P consists of the decision problems solvable by a deterministic Turing machine — the standard idealised computer, whose next step is fully determined by its current state — in time bounded by $O(n^k)$ for some fixed $k$. The class NP consists of the problems for which membership can be verified quickly given a hint: a set $L$ is in NP if there is a polynomial-time procedure $V$ and a polynomial $p$ such that $x \in L$ exactly when some string $w$ with $|w| \le p(|x|)$ makes $V(x,w)$ accept. That $w$ is the certificate — a satisfying assignment, a tour, a factorisation. Everything in P is in NP, since a machine that can solve a problem may ignore the hint. Whether the containment is strict is the open question. What makes the question sharp is NP-completeness . Cook proved in 1971 that every problem in NP can be transformed, in polynomial time, into an instance of Boolean satisfiability — SAT, the problem of deciding whether a formula built from variables, ANDs, ORs and NOTs has an assignment making it true. A problem in NP that is at least as hard as everything else in NP is called NP-complete. One polynomial-time algorithm for SAT would therefore collapse P and NP; one proof that SAT has none would separate them. The Travelling Salesperson Problem in decision form — given $n$ cities, their pairwise distances and a bound $k$, is there a tour of total length at most $k$? — is NP-complete too, and is the example most often used to argue that such problems are self-evidently intractable. Why "these problems are obviously hard" is not the difficulty This section takes the argument from combinatorial explosion at its strongest and shows that even so it establishes nothing about P versus NP. Consider the Travelling Salesperson Problem by exhaustive search. A tour is a cyclic order, so nothing is lost by fixing which city comes first; the remaining $n-1$ cities may then be arranged in any of $(n-1)!$ orders, and when the distance from city $i$ to city $j$ equals the distance from $j$ to $i$, each tour and its reverse have equal length, leaving $(n-1)!/2$ distinct candidates. Dividing by one city and by two directions are the only savings available to a method that inspects every tour. Exhaustive search is not the best known method, and the cost of the better one can be counted exactly. The standard dynamic programme over subsets keeps a state $(S, j)$: a subset $S$ of cities already visited, and the city $j \in S$ at which the partial tour ends. For each state it stores the length of the shortest path starting at the fixed origin, covering exactly $S$, ending at $j$. There are $2^n$ subsets and at most $n$ endpoints, hence at most $n \cdot 2^n$ states, and each is computed by minimising over the at most $n$ possible predecessors of $j$. States times work per state gives $O(n^2 2^n)$. For $n = 20$ that is about $400 \times 2^{20} \approx 4.2 \times 10^{8}$ operations against $19! \approx 1.2 \times 10^{17}$ tours — eight orders of magnitude, and still exponential. Now notice what that pair of counts does not show. Two particular algorithms are slow; nothing follows about the algorithm nobody has thought of. To prove $P \neq NP$ one must establish a claim quantified over every deterministic procedure, including those not yet invented: each either errs or exceeds every polynomial bound on infinitely many inputs. The slowness of the algorithms we happen to know is evidence about us, not about the problem. The honest measure of the distance to such a claim is the lower-bound record: in the general Boolean circuit model, which is if anything more generous to the prover than the Turing machine model, the largest size lower bound proved for an explicit function in NP is linear in $n$ (Arora and Barak, 2009), where a separation requires superpolynomial. That gap is not a missing trick. The following three theorems say why. The first barrier: relativisation The first barrier explains why the diagonalisation arguments that founded complexity theory cannot reach P versus NP. An oracle is a fixed set $O$ of strings that a machine may consult: it writes a string on a special tape and learns in one step whether that string lies in $O$. Writing $P^O$ and $NP^O$ for the classes defined exactly as before but with every machine given access to $O$, one may ask the question separately inside each oracle world. Most foundational results survive the addition of an oracle unchanged. The time hierarchy theorem — more time strictly buys more computing power, so that there are problems solvable in time $n^3$ but not in time $n^2$ — is proved by building a machine that simulates every faster machine on its own description and then does the opposite. Hand every machine in that proof the same oracle: the simulator passes its simulated machine's queries straight through at no extra asymptotic cost, and every line still holds. Such a proof is said to