# Many-One Reductions vs Turing-Reductions and PH

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?

-

## migrated from cstheory.stackexchange.comNov 25 '11 at 15:24

This question came from our site for theoretical computer scientists and researchers in related fields.

## 1 Answer

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.

-
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