patternMinor
A containment result in complexity
Viewed 0 times
resultcontainmentcomplexity
Problem
A question on the interesting result in http://arxiv.org/pdf/1110.6126v1.pdf
It is shown $\Pi_2^P \not\subset P^{NP}$. But http://en.wikipedia.org/wiki/Polynomial_hierarchy says $\Pi_2^P = CoNP^{NP}$.
Does this mean an oracle in NP under which $P$ is not $CoNP$ has been shown?
Could someone elaborate?
It is shown $\Pi_2^P \not\subset P^{NP}$. But http://en.wikipedia.org/wiki/Polynomial_hierarchy says $\Pi_2^P = CoNP^{NP}$.
Does this mean an oracle in NP under which $P$ is not $CoNP$ has been shown?
Could someone elaborate?
Solution
Aaronson's result shows that $\Pi_2 \not\subset P^{N\!P}$ relative to a random oracle with probability 1. As he mentions, it had already been known that $N\! P != \mathrm{co}N\! P$ (and so $P \neq N\!P$ and $P \neq \mathrm{co}N\!P$) relative to a random oracle with probability 1: see the paper by Bennett and Gill. An oracle with respect to which $P \neq N\!P$ (and so $P \neq \mathrm{co}N\!P$) had been constructed earlier by Baker, Gill and Solovay. The construction is standard, and you can find many references online.
Context
StackExchange Computer Science Q#14646, answer score: 4
Revisions (0)
No revisions yet.