Oracles, Relativization, and the Limits of Diagonalization

An oracle machine is a Turing machine with an extra tape and three special states. Writing a string on the oracle tape and entering the query state causes the machine, in one step, to learn whether that string belongs to a fixed language $O$ and to branch accordingly. The machine’s own steps are counted; the oracle’s answer is free. Every complexity class has a relativized version obtained by allowing machines oracle access, written with a superscript: $\mathrm{P}^O$, $\mathrm{NP}^O$, and so on. The study of these classes began as a technical convenience and turned into the sharpest known limit on proof techniques in complexity theory, because the answers to the central questions change when the oracle changes, and any proof that treats machines as black boxes must give the same answer in every relativized world.

What relativization preserves

Almost every elementary construction relativizes. The simulation of a multitape machine by a single-tape machine relativizes, because the simulating machine can carry the oracle tape along and issue the same queries. The closure of NP under polynomial-time reductions relativizes, because the reduction’s output is fed to a verifier that may consult the oracle. The Cook–Levin encoding relativizes: the tableau construction works with oracle states as ordinary states, provided the query strings are written in the tableau and the answers are consistent across rows.

The reason is structural. These proofs manipulate machines as syntactic objects: they simulate one machine by another, or they transform an input, or they build a formula whose variables describe a computation. None of them inspects the machine’s internal computation in a way that would break if the machine had an extra tape. The proofs are black-box in the precise sense that they use only the fact that the machine is a finite object with a step relation, not any property of what it computes.

The relativizing proofs share a second feature: they go through simulation and diagonalization. A machine that simulates another can simulate an oracle machine by simulating the oracle queries too. A diagonal machine that enumerates machines can enumerate oracle machines, provided the oracle is fixed. So the two techniques that produce almost all separation results in the subject are exactly the two that survive relativization.

Two oracles, two answers

The central result is that there exist computable oracles $A$ and $B$ with

$$\mathrm{P}^A = \mathrm{NP}^A \quad \text{and} \quad \mathrm{P}^B \ne \mathrm{NP}^B.$$

Both are constructed, and the constructions are short enough to summarize.

The collapsing oracle. Take $A$ to be any PSPACE-complete language, for instance the language of true quantified boolean formulas. Then $\mathrm{P}^A = \mathrm{NP}^A = \mathrm{PSPACE}$. The upper bound is that a polynomial-time machine with a PSPACE oracle can be simulated in polynomial space: the simulation runs the machine, and whenever it queries the oracle it solves the PSPACE-complete problem directly, which costs polynomial space because the query string has polynomial length. The lower bound is that PSPACE-hardness gives the reverse containment: a PSPACE machine can be simulated by a polynomial-time machine with a PSPACE-complete oracle, since the oracle answers exactly the questions the simulation needs. So both classes collapse to PSPACE, and in particular they are equal.

The mechanism is that the oracle is so strong that the machine’s own polynomial time is irrelevant. The class is determined by the oracle, not by the machine.

The separating oracle. The construction of $B$ is a diagonal argument carried out against all polynomial-time oracle machines simultaneously. Enumerate the machines $M_1, M_2, \dots$ with oracle access. At stage $i$, choose a length $n_i$ larger than any length considered so far, and decide which strings of that length belong to $B$ in a way that defeats $M_i$. The defeat uses the fact that $M_i$ makes at most polynomially many queries on inputs of length $n_i$, so most of the $2^{n_i}$ strings of that length go unqueried. Set $B$ to include an unqueried string of length $n_i$ if $M_i$ rejects $0^{n_i}$, and to exclude all of them if $M_i$ accepts.

def build_oracle(machines, lengths):
    # machines: polynomial-time oracle machines on input 0^n
    B = set()
    for i, M in enumerate(machines):
        n = lengths[i]                 # grows faster than any fixed polynomial
        queried = run_and_collect(M, '0' * n, B)
        all_strings = {format(k, f'0{n}b') for k in range(2 ** n)}
        unqueried = sorted(all_strings - queried)
        if M.decision == 'reject' and unqueried:
            B.add(unqueried[0])        # makes 0^n a yes-instance of L_B
    return B

The language used for the separation is the set of strings $0^n$ such that $B$ contains some string of length $n$. This language is in NP relative to $B$ for every $B$, because a nondeterministic machine guesses the string and queries the oracle once: the guess costs $n$ steps and the query is answered in one. The diagonal ensures that no polynomial-time machine with oracle $B$ decides $L_B$: on input $0^{n_i}$, the machine $M_i$ queries only polynomially many strings of length $n_i$, so it leaves at least one unqueried, and $B$ was set so that the answer to $L_B$ on that input is the opposite of what $M_i$ concludes.

The subtlety is consistency. Setting $B$ at stage $i$ must not invalidate the defeats achieved at earlier stages. This is handled by choosing the lengths $n_i$ to grow so fast that a machine defeated at length $n_i$ cannot, at a later length, produce a computation that contradicts the earlier decision. Since the machine’s running time is polynomial, and the lengths grow faster than any polynomial, the machine’s queries at length $n_{i+1}$ cannot reach back to the strings fixed at length $n_i$. The growth condition is the same device that appears in the Ladner construction, used for the same reason.

The barrier, stated precisely

A proof relativizes if, whenever it establishes a statement about unrelativized classes, the same argument establishes the corresponding statement for every oracle. The two constructions above show that the statement $\mathrm{P} = \mathrm{NP}$ is true in some relativized worlds and false in others. Therefore no relativizing proof can establish $\mathrm{P} \ne \mathrm{NP}$, and no relativizing proof can establish $\mathrm{P} = \mathrm{NP}$ either.

The conclusion is a constraint on technique, not a statement about the world. One of the two classes of worlds is the actual one, and the question has a definite answer. What the barrier shows is that the answer cannot be reached by an argument whose validity is independent of the oracle.

This is why the hierarchy theorems are on the safe side of the barrier. They are proved by diagonalization against a fixed machine model, and the same proof works with an oracle, so the separations they establish hold in every relativized world. The time hierarchy theorem separates deterministic time classes uniformly, and no oracle can collapse them, because the diagonal machine can always simulate the smaller class’s machines.

What escapes the barrier

Two families of techniques are known to escape relativization, and both are worth knowing because they define the current frontier.

Arithmetization. The proof that $\mathrm{IP} = \mathrm{PSPACE}$, that interactive proofs with polynomial rounds capture polynomial space, represents boolean formulas as polynomials over a finite field and uses the algebraic structure of those polynomials. The technique does not relativize, because the algebraic identities it relies on are not preserved by adding an oracle. The result itself is false in some relativized worlds, which is consistent with the technique’s non-relativizing character.

Circuit lower bounds via combinatorial properties. Results that exploit a specific property of the computation, such as its sensitivity to input bits, its algebraic degree, or its communication structure, can avoid the black-box assumption. The known lower bounds for restricted circuit classes fall here. They do not settle P versus NP, and they do not relativize in the strict sense, though some of them relativize to restricted oracle families.

Neither technique has produced a separation of P from NP. The barrier is not a proof that no proof exists, and the history of the subject includes results that were thought to be blocked and were not.

Oracle access as a design tool

Beyond the barrier, oracles are a working tool for relating classes. The technique is to choose an oracle that makes one class collapse into another, then read a containment off the collapse.

Take $O$ to be any PSPACE-complete language. The first step is that $\mathrm{P}^O = \mathrm{NP}^O = \mathrm{PSPACE}$. The upper bound is that a polynomial-time machine with such an oracle can be simulated in polynomial space: the simulation runs the machine and answers each query by solving the PSPACE-complete problem directly, which costs polynomial space because the query has polynomial length. The lower bound is that a PSPACE machine is simulated by a polynomial-time oracle machine, since every question it needs answered is one the oracle answers. The second step is that NP is contained in NP with access to $O$, because a machine may ignore its oracle, and NP with access to $O$ is PSPACE by the collapse. So $\mathrm{NP} \subseteq \mathrm{PSPACE}$ follows from a relativized equality plus an unrelativized simulation.

The technique also produces negative results about proof strategies. If a proposed proof of $\mathrm{P} \ne \mathrm{NP}$ would relativize, the two-oracle theorem refutes it without examining the proof’s details. This is a cheap filter, and it has been applied to several published arguments.

The oracle tape’s cost

One detail is easy to miss: the oracle answers in one step regardless of the query’s length, and this is what makes the model different from a subroutine call. A query string of length $m$ is written on the tape in $m$ steps, and the answer is free, so the cost of using the oracle is the cost of writing the query. A machine that makes polynomially many queries of polynomial length therefore spends polynomial time on queries, which is why the relativized classes are still defined by polynomial bounds.

If the oracle charged by the query length, the model would be equivalent to a subroutine call and the relativized classes would coincide with the unrelativized ones in most cases. The free answer is the whole point: it models a world in which a hard problem has been solved and the solution is available as a primitive, and it asks what the rest of the complexity landscape looks like in that world.

The answer, as the two-oracle theorem shows, is that the landscape depends on which problem was solved. That dependence is the barrier, and it is why the subject’s central question has resisted the techniques that settled everything around it.