Relativization and Oracle Separations

Fifty years of effort by the world's best logicians and theorists have not settled the P vs NP question. Why? Part of the answer is a theorem from 1975 by Theodore Baker, John Gill, and Robert Solovay: the tools that work for nearly everything else in mathematics cannot work here.

The key concept is an oracle — an imaginary black box that answers membership questions about some fixed set in a single step, regardless of how hard computing those answers actually is. When we write $P^{A}$, we mean the class of problems solvable in polynomial time with free access to oracle A. Similarly $NP^{A}$ means NP relative to A.

Baker, Gill, and Solovay proved two surprising facts at once:

• There exists an oracle A such that $P^{A}$ = $NP^{A}$ — relative to A, the two classes coincide.
• There exists an oracle B such that $P^{B}$ ≠ $NP^{B}$ — relative to B, they are provably different.

These two facts together form the relativization barrier: any proof of P = NP or P ≠ NP that works relative to every oracle would have to simultaneously prove both $P^{A}$ = $NP^{A}$ and $P^{B}$ ≠ $NP^{B}$ for the same proof, which is impossible. Since virtually all classical proof techniques relativize — they work the same way regardless of what oracle is attached — they are blocked by this barrier.

The consequence is striking: we need fundamentally new mathematics to solve P vs NP, mathematics that somehow cares about the internal structure of problems in a way that oracles can erase.

The simulation below models a simplified oracle machine. Oracle A (the "equalizing" oracle) answers questions about a PSPACE-complete set — so $NP^{A}$ collapses into $P^{A}$ because the oracle short-circuits the search. Oracle B (the "separating" oracle) is a random sparse set chosen so that any $NP^{B}$ machine asking the right questions cannot be simulated in polynomial time.

Toggle between the two oracles and run the polynomial-time machine. You will see the machine succeed in the A-world ($P^{A}$ = $NP^{A}$) and fail in the B-world ($P^{B}$ ≠ $NP^{B}$) — the same code, opposite outcomes, depending only on what oracle is plugged in.

<div class="controls">
  <div class="oracle-btns">
    <button id="btnA" class="oracle-btn active" type="button">Oracle A &nbsp;<span class="badge">P<sup>A</sup> = NP<sup>A</sup></span></button>
    <button id="btnB" class="oracle-btn" type="button">Oracle B &nbsp;<span class="badge">P<sup>B</sup> ≠ NP<sup>B</sup></span></button>
  </div>
  <button id="btnRun" type="button" class="run-btn">{{btn_run}}</button>
</div>
<div class="world-desc" id="worldDesc"></div>
<div class="log-box" id="log"></div>
<div class="result-box" id="result"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #1a1a2e; }
.controls { display: flex; flex-direction: column; gap: .6rem; margin-bottom: .7rem; }
.oracle-btns { display: flex; gap: .5rem; flex-wrap: wrap; }
.oracle-btn { font: 600 14px system-ui; padding: .4rem 1rem; border: 2px solid #4a6fa5; border-radius: 8px;
              background: #fff; color: #4a6fa5; cursor: pointer; transition: all .15s; }
.oracle-btn.active { background: #4a6fa5; color: #fff; }
.oracle-btn .badge { font-size: .78em; opacity: .9; }
.run-btn { font: 600 14px system-ui; padding: .45rem 1.1rem; border: 2px solid #1d3557;
           background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; align-self: flex-start; }
.run-btn:disabled { opacity: .5; cursor: not-allowed; }
.world-desc { font-size: .88rem; color: #444; background: #f0f4fa; border-left: 3px solid #4a6fa5;
              padding: .5rem .8rem; border-radius: 0 6px 6px 0; margin-bottom: .6rem; min-height: 2.4rem; }
.log-box { font: 13px ui-monospace, monospace; background: #0d1117; color: #e6edf3;
           border-radius: 8px; padding: .7rem 1rem; min-height: 120px; max-height: 180px;
           overflow-y: auto; white-space: pre-wrap; margin-bottom: .6rem; }
.log-box .step { color: #8b949e; }
.log-box .oracle-call { color: #79c0ff; }
.log-box .accept { color: #56d364; font-weight: 700; }
.log-box .reject { color: #f85149; font-weight: 700; }
.result-box { font: 700 1rem system-ui; padding: .6rem 1rem; border-radius: 8px; min-height: 2rem;
              display: flex; align-items: center; gap: .5rem; }
.result-box.success { background: #d1fae5; color: #065f46; border: 1.5px solid #6ee7b7; }
.result-box.failure { background: #fee2e2; color: #991b1b; border: 1.5px solid #fca5a5; }
.result-box.idle { background: #f1f5f9; color: #64748b; border: 1.5px solid #cbd5e1; }

// Code not found

Notice that the machine itself does not change — only the oracle does. This is exactly Baker, Gill, and Solovay's point: the behaviour of a proof strategy that only manipulates oracle calls can be flipped just by swapping the oracle. Any argument of that kind cannot commit to P = NP or P ≠ NP.

Relativization is a proven barrier, not a conjecture. The status of P vs NP itself remains open — one of the seven Millennium Prize Problems — but the relativization theorem is settled mathematics from Baker, Gill, and Solovay (1975).

What the theorem proves:

• Oracle A (P = NP world): Let A be a PSPACE-complete language. Then $NP^{A}$ ⊆ $PSPACE^{A}$ = PSPACE ⊆ $P^{A}$, so $P^{A}$ = $NP^{A}$. Any $NP^{A}$ machine can be simulated in polynomial time using A because A already encodes the hardest search.
• Oracle B (P ≠ NP world): A random oracle B (or a carefully constructed sparse set) gives $NP^{B}$ problems that require exponential time even with B's help, because B provides no useful shortcut for the specific language in question.

Why this blocks proofs:

Most proofs in complexity theory — diagonalization, simulation arguments, padding — relativize: they apply equally well when every Turing machine is upgraded with an oracle tape. If your proof works relative to every oracle, it would need to prove $P^{A}$ = $NP^{A}$ and $P^{B}$ ≠ $NP^{B}$ simultaneously, which is a contradiction.

Later barriers extend the picture:

• Algebrization (Aaronson and Wigderson, 2009): even algebraic extensions of oracle access — treating polynomials over finite fields rather than bit strings — cannot resolve P vs NP. This blocks IP = PSPACE–style arguments from being recycled.
• Natural proofs (Razborov and Rudich, 1994): any "natural" circuit lower-bound technique strong enough to separate P from NP would also break pseudorandom generators, which would be a cryptographic catastrophe. Unless one-way functions don't exist, natural proofs cannot work.

Together these barriers explain why P vs NP is so uniquely resistant: it seems to require techniques that are simultaneously non-relativizing, non-naturalizing, and non-algebrizing — a very narrow target.

Related reading: P vs NP · halting problem

Understanding relativization is not merely academic — it actively shapes what researchers try and what they avoid:

• Proof strategy triage: Before spending years on a new approach to P vs NP, theorists now check whether it relativizes. If it does, it is immediately disqualified as a potential proof of P ≠ NP (or P = NP). The barrier acts as an automatic filter.
• Oracle results as evidence: When researchers prove $P^{A}$ = $NP^{A}$ for some A, it signals that the techniques used in that proof cannot separate P from NP. Oracle results tell us what kinds of evidence are worthless, not just which worlds are possible.
• Cryptography and one-way functions: The natural-proofs barrier connects directly to the existence of cryptographic one-way functions. If P ≠ NP is proven with a natural proof, it would destroy standard cryptography — so any valid proof must be non-natural.
• Interactive proofs and IP = PSPACE: The landmark result IP = PSPACE (Shamir, 1992) is non-relativizing — there exist oracles where $IP^{A}$ ≠ $PSPACE^{A}$. This was the first major result that had to be non-relativizing, showing such results are possible and pointing the way forward.
• Teaching the limits of logic: Relativization is the clearest example of a meta-theorem — a theorem not about a problem but about which methods can solve a problem. It belongs to a rare class of results that rules out entire proof strategies rather than individual claims.

Relativization delivers a humbling message: the most natural ways to prove things about computation are provably insufficient for the hardest question we have. Baker, Gill, and Solovay did not prove P ≠ NP — they proved that you cannot prove it (or its opposite) with standard tools.

The silver lining is that the barrier tells us exactly where to look. The landmark results that have advanced complexity theory — IP = PSPACE, the PCP theorem, circuit lower bounds — are all non-relativizing. They peek inside the structure of computations in ways that oracle calls cannot capture. The path forward is narrow but it is not empty.

Until someone finds that non-relativizing, non-naturalizing, non-algebrizing argument, the P vs NP question remains open, guarded by a moat of its own mathematical depth. And that depth, strange as it sounds, is itself one of the most interesting things we know about the problem.

Related: P vs NP · halting problem