Symptom

You have read T026 and T027 and you are wondering the obvious thing.

Fifty years. Thousands of researchers. A million-dollar prize. And P vs NP has not moved. That is strange — most famous problems yield partial results, near misses, special cases that suggest the shape of the answer. Here there is almost nothing. We cannot even prove that NP requires more than linear-size circuits, which is a laughably weak statement compared to what everyone believes.

Is the problem just very hard, or is something structurally wrong with the way we attack it?

It is the second, and we know this precisely, because there are theorems about it. Two of them, and they kill different things. This is the rare case where a field has mapped its own failure and can tell you exactly which tools cannot possibly work.

Statement

The relativization barrier (Baker–Gill–Solovay, 1975). There exist oracles $A$ and $B$ with $\text{P}^A = \text{NP}^A$ and $\text{P}^B \ne \text{NP}^B$. Consequently, any proof technique that goes through unchanged when both classes are given the same oracle cannot resolve P vs NP — it would have to prove both outcomes.

The natural proofs barrier (Razborov–Rudich, 1994). Call a circuit lower bound argument natural if it proceeds by exhibiting a property of Boolean functions that is (i) constructive — checkable in time polynomial in the truth table — and (ii) large — held by a substantial fraction of random functions. If strong pseudorandom generators exist, no natural property can separate P from NP.

The sting is the hypothesis. Pseudorandom generators of the required strength follow from standard cryptographic assumptions, so the natural-proofs barrier says: if cryptography works, the obvious way to prove circuit lower bounds does not. Believing hardness is what blocks proving hardness.

Algebrization (Aaronson–Wigderson, 2008) closes the remaining gap: the arithmetization techniques that beat relativization, which gave us IP = PSPACE, still fail against a slightly extended notion of oracle access.

Three barriers, and the known techniques fall into their union.

Argument

Relativization, via oracles. An oracle is a black box answering membership queries in one step. $\text{P}^A$ is what polynomial machines decide with free access to $A$. Most classical arguments — diagonalization, simulation — do not care what the machine does internally, so they hold verbatim when both classes get the same oracle. Baker, Gill and Solovay showed this is fatal.

An oracle collapsing them. Let $A$ be any PSPACE-complete language. With $A$ in hand, a polynomial machine can decide anything in PSPACE, and PSPACE is closed under the nondeterministic guessing NP does, so $\text{P}^A = \text{NP}^A = \text{PSPACE}$. One oracle, both classes flattened.

An oracle separating them. Build $B$ by diagonalization. Let $L_B = {1^n : B \text{ contains some string of length } n}$. Clearly $L_B \in \text{NP}^B$: guess the string, query it. Now construct $B$ in stages against an enumeration of polynomial-time oracle machines. At stage $i$, pick a length $n$ larger than anything decided so far, run machine $M_i$ on $1^n$, and watch: it makes at most $n^{k}$ queries, but there are $2^n$ strings of length $n$, so for large $n$ it must leave one unqueried. If $M_i$ accepts, put no length-$n$ string in $B$; if it rejects, add an unqueried one. Either way $M_i$ is wrong, and it cannot tell, because its answers do not change. So $L_B \notin \text{P}^B$.

The technique is a counting argument: a polynomial machine cannot look at exponentially many places, so we hide the answer where it did not look. This is exactly T005’s adversary argument, applied to oracles.

Why this indicts our tools. Cook–Levin’s tableau is a simulation and relativizes. The hierarchy theorems are diagonalization and relativize. Everything in the classical toolkit relativizes, so none of it can settle P vs NP.

Natural proofs, and why the plausible route is blocked. Circuit lower bounds do not relativize, so after 1975 that was the road. It worked at first: Razborov proved exponential lower bounds for monotone circuits, Håstad’s switching lemma gave parity’s lower bound for AC⁰ (T034). Then it stopped, and progress against general circuits ceased entirely.

Razborov and Rudich asked what those successful proofs had in common. All worked by exhibiting a property $P$ of Boolean functions: hard functions have $P$, and functions computed by small circuits do not. Both features are natural in practice. The property must be checkable or you cannot argue with it, and it must be common among random functions, because random functions are hard and any property capturing hardness will catch most of them.

Now the punch. A pseudorandom function family is one no efficient test distinguishes from truly random. Suppose you have a constructive, large property $P$ separating hard functions from easy ones. Then $P$ is an efficient distinguisher: pseudorandom functions are computed by small circuits, so they lack $P$; truly random functions have it with substantial probability. Compute $P$ on the truth table and you have broken the generator.

So a natural proof of strong circuit lower bounds breaks cryptography. Since we believe cryptography holds — and its security rests on the same hardness assumptions the lower bound would establish — we believe no natural proof exists. The two beliefs are the same belief, pointed in opposite directions.

Savitch’s theorem, which shows the barriers are not universal. $\text{NSPACE}(f(n)) \subseteq \text{DSPACE}(f(n)^2)$: nondeterminism buys at most a squaring in space, so NPSPACE = PSPACE. The proof is a recursive reachability test — to check configuration $c_1$ reaches $c_2$ in $2^k$ steps, guess the midpoint and recurse on both halves, reusing the same space, giving depth $O(f(n)^2)$. This is exactly the space analogue of the P vs NP question, and it is settled. Space is reusable and time is not, and that difference is why one question fell in 1970 while the other did not. It is also the sharpest available answer to “maybe the question is simply unanswerable.”

Forbids

Any relativizing proof of P ≠ NP or P = NP. Diagonalization and simulation alone, in every arrangement, are ruled out. Most amateur proofs die here.

Natural circuit lower bounds against P/poly, if strong PRGs exist. The approach that produced every circuit lower bound we have cannot be pushed to the general case.

Arithmetization alone, by algebrization. The technique that beat relativization is itself bounded, and its bound is now known.

The expectation of a short elementary proof. Any resolution must be non-relativizing, non-naturalizing, and non-algebrizing simultaneously. Nothing in the standard toolkit qualifies, so a proof will require a genuinely new idea.

Does not forbid

They do not say P vs NP is unprovable or independent of ZFC. This is the common misreading, and it is wrong. The barriers constrain techniques, not truth. There is no evidence of independence, and unlike the continuum hypothesis, no forcing construction or model-theoretic obstruction is known.

They do not stop lower bounds from being proved. Parity is not in AC⁰ (T034), unconditionally. Razborov’s monotone bound is unconditional. Ryan Williams proved NEXP $\not\subseteq$ ACC⁰ in 2011 by combining circuit analysis with a faster-than-brute-force satisfiability algorithm — explicitly non-natural, and the clearest existence proof that barrier-evading arguments exist. There is also a well-known unconditional time-space tradeoff showing SAT cannot be solved in $n^{1.8}$ time and logarithmic space simultaneously.

They do not make the barriers themselves useless. Razborov–Rudich is a specification for a working proof: your property must be non-constructive or rare. Williams’s programme deliberately targets that gap, and “which barrier does this evade” is now a standard question asked of any new technique.

They do not undermine complexity theory’s practical results. NP-hardness reductions (T028) are unaffected — those are proofs within the theory, not separations of classes. Everything you use complexity theory for at work is untouched.

They do not imply the community is stuck for lack of effort or ideas. Interactive proofs, PCP (T031), and the whole hardness-versus-randomness line came out of these decades. The field moved a great deal; it moved sideways relative to the flagship question.

Boundary

  • The barriers are about the general case. Restricted circuit classes — monotone, constant-depth, bounded fan-in, ACC⁰ — remain open ground, and that is where lower-bound progress actually happens.
  • Williams’s route: algorithms as lower bounds. A faster-than-brute-force algorithm for circuit satisfiability implies a circuit lower bound. Turning algorithm design into lower-bound proof is the most promising known barrier-evading direction.
  • Non-uniformity is a real gap. P/poly permits a different circuit per input length, including circuits computing undecidable languages. NP $\not\subseteq$ P/poly is stronger than P ≠ NP, and non-uniform lower bounds are where the circuit programme lives.
  • Proof complexity as the other flank. Lower bounds on proof length in specific systems — resolution, cutting planes, Frege — are a concrete sub-goal, since NP ≠ coNP would follow from super-polynomial lower bounds for every propositional proof system. That programme has genuine unconditional results.
  • Savitch is the standing counterexample to fatalism. The space version of the question is solved, by an argument two paragraphs long, exploiting a resource property time does not have. Knowing why space was easy is the best guide to what a time proof would need.