Relativization barrier

The relativization barrier is a fundamental obstacle in computational complexity theory, identified by Theodore Baker, John Gill, and Robert Solovay in their landmark 1975 paper. The barrier states that any proof technique that relativizes — that is, any proof that works even when all machines are given access to an arbitrary oracle — cannot resolve the P versus NP problem or any of the other major open questions in complexity theory.

An oracle is a hypothetical black box that can solve a specific problem in a single step. A proof technique relativizes if it remains valid regardless of which oracle the machines have access to. Baker, Gill, and Solovay showed that there exist oracles A and B such that P^A = NP^A and P^B ≠ NP^B. This means that any proof that works for all oracles cannot prove P = NP (because it would be contradicted by oracle B) and cannot prove P ≠ NP (because it would be contradicted by oracle A).

The relativization barrier eliminated diagonalization — the technique used to prove the space hierarchy theorem and the time hierarchy theorem — as a viable approach to P versus NP. It also ruled out many other natural proof techniques. The barrier forced complexity theorists to develop new approaches, including circuit complexity and algebraic methods, though these too have faced their own barriers: the natural proofs barrier of Razborov and Rudich, and the algebrization barrier of Aaronson and Wigderson.