1

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?

Kaveh
  • 3,572

1 Answers1

2

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.

Sasho Nikolov
  • 1,127
  • 1
    Your answer is totally the opposite of the answer to this question... http://cstheory.stackexchange.com/questions/8759/karp-like-reductions-vs-cook-like-reductions-for-functional-complexity-classes –  Nov 25 '11 at 02:48
  • 1
    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! –  Nov 25 '11 at 03:01