One oracle makes P and NP equal while another separates them - what does that rule out about proving P versus NP?

## What an oracle is An **oracle** for a language A is a black box a machine may consult: it writes a string on a query tape and is told in a single step whether that string belongs to A. Writing `P^A` for the class decidable in polynomial time by a machine with that box, and `NP^A` for the nondeterministic analogue, gives a *relativized* world. The box is free and instantaneous on purpose; the point is not to model a real subroutine but to change the ground rules for both classes at once and see what survives. ## What the oracle result shows Baker, Gill and Solovay exhibited two oracles: - an oracle A - a language rich enough that one query absorbs the difference between guessing and computing - for which `P^A` equals `NP^A`; - an oracle B, built by diagonalizing against every polynomial-time machine so that one query is always missing, for which `P^B` differs from `NP^B`. Both worlds are internally consistent. Now take any proof technique that **relativizes**, meaning its argument still reads correctly when every machine it mentions is handed the same oracle: 1. A relativizing proof that the classes are equal would also prove `P^B` equals `NP^B`, which is false. 2. A relativizing proof that they differ would also prove `P^A` differs from `NP^A`, which is also false. So **no relativizing technique can settle the question in either direction.** That is a statement about methods, not about the answer. ## Why simulation arguments relativize The hierarchy theorems work by building a machine that simulates another under a clock and flips its verdict. Nothing in that argument looks at *what* the simulated machine computes - it only steps it. Hand both machines the same oracle and every line still holds: the simulator forwards the query, the box answers, the clock ticks. Two consequences follow, and they are worth stating together because they pull in opposite directions: - The hierarchy theorems hold **relative to every oracle** - polynomial time with any oracle X is still strictly inside exponential time with the same oracle X. For them, relativizing costs nothing, because no oracle world contradicts them. - The same technique **cannot be pushed one step further** to the open questions in the chain, because it cannot distinguish worlds it never looks inside. That is the honest answer to "why has nobody just diagonalized harder": the tool is not weak, it is blind in the one place it would need to see. ## What the barrier does not say Three misreadings, all common: 1. **Not undecidable and not independent.** The result says nothing about whether a proof exists or whether the question is settled by standard axioms. It constrains the shape of a proof, not its existence. 2. **Not "diagonalization is dead".** Diagonalization proved the hierarchy theorems and remains the standard tool for separating a resource from itself. What is ruled out is the black-box form of it applied across these particular steps. 3. **Not evidence for either answer.** A world where the classes coincide is not evidence that they coincide, and the other world is not evidence that they differ. Oracle results are statements about techniques, and reading them as votes is the classic error. ## What an escaping proof would have to look like A technique that survives the barrier has to depend on the **internal structure** of a computation - the circuit of gates it unrolls to, or the algebraic form of its transition relation - rather than on the ability to step a machine. Arguments that encode a computation as a low-degree polynomial and reason about it algebraically are the standard example of non-relativizing reasoning, and they are why the barrier is a constraint rather than a verdict. Later work identified further barriers of the same flavour, each ruling out another whole family of arguments; taken together they are a large part of why these steps have resisted for decades, and why a proof announcement that uses only simulation and counting can be dismissed without reading it closely. ## Using it in an interview - Say what an oracle is before using the word, because the whole argument turns on "same box for both sides". - State the conclusion in the form that is actually true: a constraint on techniques, symmetric between the two possible answers. - Connect it to the hierarchy theorems rather than treating them as unrelated: the same argument shape relativizes, which is harmless in one place and fatal in the other.