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.

Suppose a language L is in NP. I think that means a nondeterministic Turing machine M can decide it in polynomial time. But then shouldn't it be in co-NP, because can't we define a new Turing machine M' that accepts whenever M rejects and rejects whenever M accepts? Why doesn't NP equal co-NP?

Thanks!

share|improve this question
    
Removed "theoretical-cs" tag. "Applied CS" is programming, and would be off-topic. See the tag-wiki for (computer-science) –  Willie Wong Apr 15 '13 at 5:44
add comment

3 Answers 3

up vote 8 down vote accepted

That works for deterministic machines, but not for nondeterministic, since a nondeterministic machine has many "branches" in its calculation, and a language is defined to be accepted by a machine if there exists a branch that accepts it (in the normal sense, that $q_{acc}$ is reached) and rejected if all branches reject. If the machine accepted a language by reaching an accept condition on some branches and rejecting on others, flipping the conditions you end up with a machine which again accepts that language, while you intended to make a machine that rejects it.

share|improve this answer
add comment

This arises because of the asymmetry in definition of a non-deterministic Turing machine.

An NDTM accepts a language $L$, if at least one of the computation paths results in a "yes". It could so happen that there are other computation paths which result in a "no". But all we need is a single yes.

To get a "no", all the computation paths must result in a "no".

The Complement language requires at least one "no" for a "no", but all "yes" for a "yes".

So given an NDTM $M$ for $L$, you can construct a TM which runs M, and flips the output, but that is not a non-deterministic Turing machine, by definition.

If you take $M$, and just flip the accepting and rejecting states, then you won't get an NDTM for complement of $L$, as for some strings in $L$, $M$ could result in some paths saying "yes" and some paths saying "no". You will put such $x$ in the complement of $L$.

Thus it is not clear that NP = CO-NP, and it is in fact, an open problem.

share|improve this answer
add comment

Classes NP and co-NP are defined using Karp reductions (also known as a polynomial-time many-to-one reductions). A Karp reduction from language $L_1$ to $L_2$ is a polynomial-time computable function $f:\{0,1\}^*\to\{0,1\}^*$ such that $x\in L_1$ if and only if $f(x) \in L_2$. Note that there are no negations in this definition! E.g., if $x\in L_1$ if and only if $f(x) \notin L_2$, then $f$ is not a Karp reduction from $L_1$ to $L_2$.

What you describe in your question is a Cook reduction (also known as a polynomial-time Turing reduction). Every Karp reduction is a Cook reduction but not vice versa. If classes NP and co-NP were defined using Cook reduction then we would have $NP_{Cook}=$ co-NP $_{Cook}$. Note that your argument indeed shows that if $P=NP$ then $P=$ co-NP.

share|improve this answer
    
I don't see how this is answering the question. NP and co-NP are well defined without any reductions. –  Aryabhata Apr 14 '13 at 17:21
    
@Aryabhata, yes. But read the question: the OP constructs a reduction from NP to co-NP and asks why don't the existence of such reduction proves that NP=co-NP. If it was a Karp reduction, its existence would indeed prove that NP=co-NP. But since it is a Cook reduction, it doesn't prove that. –  Yury Apr 14 '13 at 17:24
    
The formal answer would be "you can do what you described an so what, why does it prove anything?". –  Yury Apr 14 '13 at 17:27
    
The question is "why it does not prove anything?", which seems to be a valid question. There are no reductions in the definition of co-NP. Why is it even relevant to talk about Cook or Karp? (Note: You might be right, and this might indeed be an answer, but the question is more basic, IMO). –  Aryabhata Apr 14 '13 at 17:47
    
Now I think this answer deserves a +1, because I believe it would answer the next questions... –  Aryabhata Apr 14 '13 at 17:58
show 2 more comments

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.