[BG81] Relative to a random oracle $A$, ${\mathbf{P}}^A\ne {\mathbf{NP}}^A\ne {\mathbf{coNP}}^A$ with probability 1

Authors: Charles H. Bennett, John Gill | Venue: SIAM Journal on Computing 1981 | Source

Abstract

TODO — abstract.

BibTeX

Copy

@article{BG81,
  author  = {Charles H. Bennett and John Gill},
  title   = {Relative to a Random Oracle {$A$}, {$P^A \neq NP^A \neq \mathrm{co}\text{-}NP^A$} with Probability 1},
  journal = {SIAM Journal on Computing},
  volume  = {10},
  number  = {1},
  pages   = {96--113},
  year    = {1981},
  doi     = {10.1137/0210008},
}