[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.

BibTeX

Copy

@article{BGS75,
  author  = {Theodore Baker and John Gill and Robert Solovay},
  title   = {Relativizations of the {$\mathcal{P} =? \mathcal{NP}$} Question},
  journal = {SIAM Journal on Computing},
  volume  = {4},
  number  = {4},
  pages   = {431--442},
  year    = {1975}
}