Take the 2-minute tour ×
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|improve this question

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

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

Whomever voted to close it can you please tell me why. Thanks –  Tayfun Pay Nov 25 '11 at 1:52
I am guessing that the reason for close votes is that they feel that the question is really not research level, and is probably more suitable for Mathematics. Based on the answer to the question I have to agree with them. –  Kaveh Nov 25 '11 at 5:34
You may delete it –  Tayfun Pay Nov 25 '11 at 12:07
Since there is an answer, it wont let me delete it. You can moce it to math as well. It is okay! :-) –  Tayfun Pay Nov 25 '11 at 15:17
add comment

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
add comment

Your Answer


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