Sign up ×
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.

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|cite|improve this question

migrated from Nov 25 '11 at 15:24

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

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|cite|improve this answer
Your answer is totally the opposite of the answer to this question...… – 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


By posting your answer, you agree to the privacy policy and terms of service.