Introduction

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 PAP^{A}, we mean the class of problems solvable in polynomial time with free access to oracle A. Similarly NPANP^{A} means NP relative to A.

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

  • There exists an oracle A such that PAP^{A} = NPANP^{A} — relative to A, the two classes coincide.
  • There exists an oracle B such that PBP^{B} ≠ NPBNP^{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 PAP^{A} = NPANP^{A} and PBP^{B} ≠ NPBNP^{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.

Try It: Two Oracle Worlds

The simulation below models a simplified oracle machine. Oracle A (the "equalizing" oracle) answers questions about a PSPACE-complete set — so NPANP^{A} collapses into PAP^{A} because the oracle short-circuits the search. Oracle B (the "separating" oracle) is a random sparse set chosen so that any NPBNP^{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 (PAP^{A} = NPANP^{A}) and fail in the B-world (PBP^{B} ≠ NPBNP^{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">Run polynomial-time machine</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Relativization demo — Baker, Gill, Solovay (1975)
// We model two oracle worlds and show a polynomial-time machine
// succeeds in world A (P^A = NP^A) but fails in world B (P^B != NP^B).
//
// ORACLE A: answers membership in a PSPACE-complete language.
//   We simulate: "is there a path of length <= k in this graph?"
//   which is in PSPACE. A poly-time machine with oracle A can
//   solve NP problems by asking A directly.
//
// ORACLE B: a sparse random set. A poly-time machine can only ask
//   polynomially many queries. With high probability none of them
//   land in B, so B gives no useful information.
//
// The machine: tries to decide if a string x is in a language L_B
//   that encodes a long witness search. In world A it succeeds
//   (oracle short-circuits the search). In world B it fails
//   (oracle never helps, and brute force is exponential).

const ORACLE_A_SIZE = 16;    // universe size for oracle A
const ORACLE_B_SIZE = 256;   // universe size for oracle B (sparse)
const B_DENSITY = 3;         // only 3 elements are in B (sparse!)
const POLY_BUDGET = 12;      // poly-time machine query budget

let currentOracle = 'A';

// Build oracle A: first ORACLE_A_SIZE/2 elements are "in" (dense half)
const oracleA = new Set();
for (let i = 0; i < ORACLE_A_SIZE / 2; i++) oracleA.add(i);

// Build oracle B: sparse — only 3 elements in [0, ORACLE_B_SIZE)
// All three are ABOVE the poly budget (12), so the machine never hits them.
// Fixed: 37, 83, 199
const oracleB = new Set([37, 83, 199]);

function queryOracle(oracle, x) {
  if (oracle === 'A') return oracleA.has(x);
  return oracleB.has(x);
}

// The polynomial-time machine:
// In world A, it can find an element in the oracle by querying 0..POLY_BUDGET-1.
// Since oracle A is dense (half the elements are IN), this succeeds quickly.
// In world B, it queries the same positions. Oracle B is sparse (3/256),
// so the machine almost certainly never hits a "yes" within budget.
function runMachine(oracle) {
  const log = [];
  let found = false;
  let foundAt = -1;

  log.push({ type: 'step', text: fmt('[MACHINE] Oracle world: %oracle%. Budget: %POLY_BUDGET% queries.', { oracle: oracle, POLY_BUDGET: POLY_BUDGET }) });
  log.push({ type: 'step', text: fmt('[MACHINE] Goal: find any x in [0,%v%).', { v: oracle === 'A' ? ORACLE_A_SIZE : ORACLE_B_SIZE }) });

  for (let q = 0; q < POLY_BUDGET; q++) {
    const answer = queryOracle(oracle, q);
    log.push({
      type: 'oracle-call',
      text: `  query(${q}) → ${answer ? 'YES (in oracle)' : 'NO'}`
    });
    if (answer) {
      found = true;
      foundAt = q;
      log.push({ type: 'accept', text: fmt('[MACHINE] ACCEPT — found x=%q% in oracle after %v% queries.', { q: q, v: q + 1 }) });
      break;
    }
  }

  if (!found) {
    log.push({ type: 'reject', text: fmt('[MACHINE] REJECT — no element found within budget of %POLY_BUDGET% queries.', { POLY_BUDGET: POLY_BUDGET }) });
  }

  return { found, foundAt, log };
}

const descriptions = {
  A: 'Oracle A is dense: half of all strings are members. A polynomial-time machine asking only a few queries will quickly find a "yes" — so Pᴬ = NPᴬ (the oracle short-circuits the NP search).',
  B: 'Oracle B is sparse: only 3 of 256 strings are members (density < 1.2%). The machine’s polynomial query budget is very unlikely to hit any of them — so it cannot harness B, and Pᴮ ≠ NPᴮ.'
};

function renderLog(entries) {
  const box = document.getElementById('log');
  box.innerHTML = '';
  for (const e of entries) {
    const span = document.createElement('span');
    span.className = e.type === 'oracle-call' ? 'oracle-call'
      : e.type === 'accept' ? 'accept'
      : e.type === 'reject' ? 'reject'
      : 'step';
    span.textContent = e.text + '\n';
    box.appendChild(span);
  }
  box.scrollTop = box.scrollHeight;
}

function setResult(found, oracle) {
  const box = document.getElementById('result');
  if (found) {
    box.className = 'result-box success';
    box.textContent = fmt('✓ Machine ACCEPTED in Oracle %oracle% world — Pᴬ = NPᴬ holds here.', { oracle: oracle });
  } else {
    box.className = 'result-box failure';
    box.textContent = fmt('✗ Machine REJECTED in Oracle %oracle% world — Pᴮ ≠ NPᴮ holds here.', { oracle: oracle });
  }
}

function clearResult() {
  const box = document.getElementById('result');
  box.className = 'result-box idle';
  box.textContent = 'Press "Run polynomial-time machine" to see the outcome.';
}

function setWorld(oracle) {
  currentOracle = oracle;
  document.getElementById('btnA').classList.toggle('active', oracle === 'A');
  document.getElementById('btnB').classList.toggle('active', oracle === 'B');
  document.getElementById('worldDesc').textContent = descriptions[oracle];
  document.getElementById('log').innerHTML = '';
  clearResult();
}

document.getElementById('btnA').addEventListener('click', () => setWorld('A'));
document.getElementById('btnB').addEventListener('click', () => setWorld('B'));
document.getElementById('btnRun').addEventListener('click', () => {
  const btn = document.getElementById('btnRun');
  btn.disabled = true;
  const { found, log } = runMachine(currentOracle);
  renderLog(log);
  setResult(found, currentOracle);
  btn.disabled = false;

  // Verification trace for node (console.log)
  console.log('Oracle:', currentOracle, '| | found:', found,
    '| | Oracle A members:', [...oracleA].join(','),
    '| | Oracle B members:', [...oracleB].join(','));
});

// Initialize
setWorld('A');
clearResult();
Result
Console

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.

The Real Complexity

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 NPANP^{A} ⊆ PSPACEAPSPACE^{A} = PSPACE ⊆ PAP^{A}, so PAP^{A} = NPANP^{A}. Any NPANP^{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 NPBNP^{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 PAP^{A} = NPANP^{A} and PBP^{B} ≠ NPBNP^{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

Where It Matters

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 PAP^{A} = NPANP^{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 IPAIP^{A} ≠ PSPACEAPSPACE^{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.

Conclusion

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

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/relativization/Content licensed under CC BY-NC 4.0.