[BGS75] Relativizations of the P=NP question

Authors: Theodore Baker, John Gill, Robert Solovay | Venue: SICOMP 1975 | Source

Abstract

The question of whether $\mathbf{P}=\mathbf{NP}$ is considered in the context of relativized computation. It is shown that there exist oracles $A$ and $B$ such that ${\mathbf{P}}^A={\mathbf{NP}}^A$ and ${\mathbf{P}}^B\ne {\mathbf{NP}}^B$. This demonstrates that any resolution of the P vs NP question must use proof techniques that do not relativize — i.e., techniques whose validity is not preserved when all parties are given access to an arbitrary oracle. The result established relativization as a fundamental barrier in complexity theory.