# Why isn't NP = coNP?

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!

-
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

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.

-

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.

-

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.

-
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