One definition of $\mathsf{PH}$ uses Oracles and in this definition both $\mathsf{NP}$ and $\mathsf{coNP}$ are contained in P^NP which equals $\mathsf{P^{coNP}}$. It is believed that $\mathsf{NP}$ does not equal $\mathsf{coNP}$, in other words they are not many-one reducible to each other. If indeed this is proved, then doesn't it also hold that $\mathsf{P^{NP}}$ doesn't equal $\mathsf{P^{coNP}}$ since many-one reducibility imply Turing reducibility?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
migrated from cstheory.stackexchange.com Nov 25 '11 at 15:24
|
The fact that many-one reductions are weaker than Turing reductions only means that NP = coNP implies P^NP = P^coNP, but not the converse. To illustrate this, think about the following: many-one polytime reductions are weaker than many-one exponential time reductions. But even though P and EXP are not equal by the time hierarchy, they are exp-time reducible to each other. |
|||||
|
