Take the 2-minute tour ×

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?

share|improve this question

migrated from cstheory.stackexchange.com Nov 25 '11 at 15:24


1 Answer 1

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.

share|improve this answer
Your answer is totally the opposite of the answer to this question... cstheory.stackexchange.com/questions/8759/… –  Tayfun Pay Nov 25 '11 at 2:48
So if A is many-one reducible to B then it means A is Turing reducible to B. If A is not many-one reducible to B then it doesn't necessarily mean that A is not Turing reducible to B. OKAY!!!! Phew! –  Tayfun Pay Nov 25 '11 at 3:01

Your Answer

