The Relativization Barrier: Why It's Hard to Resolve P vs NP

Give a Turing machine more time and it can solve strictly more problems. That is the time hierarchy theorem, and its proof, diagonalization, drew the first sharp lines in complexity theory. This is the story of the day that technique hit a wall, and of exactly what the wall is made of.

The trick that built the hierarchy#

We want a problem solvable in $n^2$ time that cannot be solved in $n$ time. Enumerate all Turing machines $M_1,M_2,M_3$, and so on. Build a machine $D$ that, on input $x$, simulates the $x$-th machine $M_x$ on input $x$ with a clock counting down $n$ steps. If $M_x$ accepts within the budget, $D$ rejects; otherwise $D$ accepts. $D$ flips the answer.

$D$ itself runs in about $n^2$ time, the overhead of step-by-step simulation, and by construction it disagrees with every $n$-time machine on at least one input: with $M_x$ at a large enough input $x$. So the language $D$ decides is in DTIME($n^2$) but not in DTIME($n$). The same trick works at every level, so more time always buys you something. Diagonalization settled "does more time help?" and "does more space help?", and the natural next target was the central open problem: does P equal NP?

In 1975, Theodore Baker, John Gill, and Robert Solovay proved that diagonalization cannot answer that question. Not because the question is too hard, but because the technique is too general. It works in settings where P equals NP and in settings where it doesn't. A tool that cuts everything cuts nothing.

Oracles#

The argument rests on a concept Turing introduced in 1939. An oracle is a black box: write a string on a special tape, enter a query state, and in one step, regardless of the string's length, the oracle answers yes or no, depending on whether the string belongs to some fixed language $A$. A machine with access to oracle $A$ is written $M^A$; it runs normally except that it can query the oracle at any point and the answer arrives instantly. From this you get relativized classes: $P^A$ is what deterministic polynomial-time machines with oracle $A$ can decide, and $N{P}^A$ is the same for nondeterministic machines, or equivalently for verifiers checking polynomial-length certificates with oracle access.

Now attach an oracle to every machine in the time hierarchy proof. To simulate a machine that has an oracle, you forward its queries to your own oracle, and the diagonalization goes through unchanged: the hierarchy theorem holds for every oracle $A$. The same is true of the proof that P is contained in NP, of NP inside PSPACE, of Savitch's theorem. These proofs are black-box, treating the machine as something you simulate and count steps on. We say such results relativize.

The oracle that collapses P and NP#

Baker, Gill, and Solovay constructed two oracles. The first makes P equal NP. Let $A$ be TQBF, the set of true quantified Boolean formulas, which is PSPACE-complete: every PSPACE problem translates into a TQBF instance in polynomial time.

One direction: PSPACE is contained in $P^A$, because a polynomial-time machine with oracle $A$ reduces its input to a TQBF instance and queries the oracle. The other: $N{P}^A$ is contained in PSPACE. Cycle through all possible certificates; for each, simulate the verifier step by step, and whenever it queries the oracle, answer by running the polynomial-space decision procedure for TQBF, then reclaim the space and continue. Chaining the two:

$$P^A=PSPACE=N{P}^A.$$

The oracle is so powerful it swamps the P versus NP distinction. That was the easy direction. The real question is whether an oracle can create a distinction that isn't there without one.

The oracle that separates them#

The oracle $B$ is a set of binary strings, and we get to choose which. A polynomial-time machine can only look at polynomially many strings, but there are exponentially many at each length. Concretely: a machine running in time $n^3$, working at length 30, faces over a billion strings of that length but can make at most ${30}^3=27,000$ queries. It sees a sliver and has to guess about the rest.

Ask it a simple question: does the oracle contain any string of this length? A nondeterministic machine answers easily, by guessing a string and querying it. A deterministic machine must commit after seeing its sliver. If it says yes, we put nothing of length 30 in the oracle; it was wrong. If it says no, we pick one of the billion-minus-27,000 strings it never asked about and put it in; it was wrong. Either way the machine loses, and the reason is purely arithmetic: polynomial is much smaller than exponential.

Now scale up. List every polynomial-time oracle machine; for each, pick a fresh length, large enough that its query budget is dwarfed by the number of strings, and defeat it there. The stages don't interfere because each operates at its own length. The language $L_B$, "does $B$ contain a string of length $n$?", is in $N{P}^B$ but not in $P^B$.

Pause and try: why doesn't the same adversary argument defeat the nondeterministic machine?

The adversary's move depends on watching a single computation unfold and then planting a string it never queried. A deterministic machine has one computation path, so this works. A nondeterministic machine deciding $L_B$ has a branch for every possible guess: whichever string the adversary plants, the branch that guessed exactly that string queries it and accepts, and if nothing is planted, every branch correctly fails. The machine's answer tracks the oracle's contents across all exponentially many branches at once, leaving the adversary nothing to flip.

The trap closes#

Step back. Oracle $A$ makes the classes equal; oracle $B$ separates them. Now suppose a proof technique relativizes, meaning the same argument goes through with any oracle attached. If it proves P is not equal to NP, it also proves $P^A\ne N{P}^A$, contradicting oracle $A$. If it proves P equals NP, it also proves $P^B=N{P}^B$, contradicting oracle $B$. Either way it would be proving something true in one oracle world and false in another. No relativizing proof can settle P versus NP.

In 1981, Bennett and Gill pushed further: relative to a random oracle, P is not equal to NP with probability one. The separation is the generic case. Oracle $A$, the one that makes them equal, is the exception.

Why diagonalization is blind#

Why does diagonalization relativize? Look at what $D$ actually does: it simulates another machine step by step, without caring what the machine computes. When the simulated $M_x$ enters its query state, $D$ simply forwards the string to its own oracle and writes the answer back into the simulation. The query passes straight through, uninspected. Swap in a different oracle and $D$ doesn't notice: same simulation, same flip, same conclusion in every oracle world, including oracle $A$'s world where P equals NP. It is not that the technique is weak. It is blind. To separate P from NP, a proof must see something $D$ cannot: the structure of the computation, not its input-output behavior alone.

Life after the barrier#

Solovay was a set theorist, an expert in independence proofs, and the oracle constructions have a deep parallel with forcing, the technique Cohen used for the continuum hypothesis. Different oracles are different mathematical universes, and a technique that cannot distinguish universes cannot settle a question whose answer varies across them.

Before 1975, the field expected diagonalization, or some refinement, to resolve P versus NP the way it had resolved every earlier separation. The response to the barrier was to seek inherently non-relativizing techniques, and circuits were the natural candidate: a Boolean circuit is a finite, non-uniform object with no oracle tape. The 1980s circuit program followed, from the Furst-Saxe-Sipser and Ajtai lower bounds for parity in constant depth, through Yao's exponential bounds and Håstad's switching lemma, to Razborov's superpolynomial bounds for monotone circuits computing clique. Then it stalled on general circuits, and in 1994 Razborov and Rudich explained why: the natural proofs barrier, a wall of its own.

But non-relativizing proofs do exist. In 1988, Fortnow and Sipser constructed an oracle relative to which coNP is not contained in IP, so when Shamir, building on Lund, Fortnow, Karloff, and Nisan, proved IP equals PSPACE in 1990, the proof was provably non-relativizing. The technique is arithmetization: converting Boolean formulas into polynomials over finite fields, whose algebraic identities have no analogue an oracle can mimic. Deep results can thread past the wall.

If you remember three things#

1. Diagonalization works by simulating a machine as a black box, so it succeeds or fails identically no matter what oracle is attached.
2. There is an oracle making $P^A=N{P}^A$ and an oracle making $P^B\ne N{P}^B$, so no relativizing technique can settle P versus NP in either direction.
3. A proof of P versus NP must look inside the computation. Arithmetization proved that non-relativizing techniques exist, but a second wall, natural proofs, stands behind the first.