Why isn't NP = coNP?

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

One way to think about it is that negating the output of a polynomial-time TM that decides $L\in\mathbf{P}$ produces an algorithm for deciding $\overline L$, and that algorithm happens to be easily implementable as a polynomial-time TM.

However, while negating the output of a polynomial-time NDTM that decides $L\in\mathbf{NP}$ does give us an algorithm for deciding $\overline L$, this algorithm is not easily implementable as a polynomial-time NDTM, due to the asymmetry described in the other answers.

Answer 5

First we need to answer the question: how does the Turing machine for NP work? There are two ways to think about it: (https://en.wikipedia.org/wiki/Nondeterministic_Turing_machine )

Way1 - Luckiest possible guesser

Way2 - Imagine that the machine branches into many copies each of which follows one of the possible transitions. If at least one branch of the tree halts with an accept condition, the NTM accepts the input

Let’s stick with thinking about the non-deterministic Turing machine in terms of “branching” into many copies (way 2).

Let’s try the machine on some problems and then we will understand why we can’t just reverse the output for NP and claim we’ve solved Co-Np in polynomial time with a Turing machine.

Let’s take a very simple problem, boolean satisfiability. Is ϕ = ((x1 ∧ x2)) SAT?

Our algorithm for solving the np-problem will be as follows:

1. Non-deterministically pick a value for x1 (our turing machine branches into 2 over here. Machine 1 sets x1 to 0 and Machine 2 sets x1 to false)

2. Non-deterministically pick a value for x2 (each turing machine further branches into 2 over here. One sets x2 to 0 and the other sets x2 to false) The final machines that will run and give out an answer are M3, M4, M5 and M6.

3. Next step is to verify whether the values for x1,x2 satisfies the problem. Remember for our non deterministic turing machine, if one of the output halts with an accept(true) condition we return True. Since one of the output is true, we get a true as an output.

Now let’s try the complement problem, is ϕ = ((x1 ∧ x2)) unsatisfiable? We will go through our same steps 1 to 3. We want to be really clever this time. So after verifying if the values we have for x1 and x2 satisfy the formula, we will just return the complement. That is, if we get true, we will return False.

Since the Turing machine returns True if one or more of the outputs is True and false otherwise and we have some of the outputs being True (eg x1=0, x2=1), when we run the IsUnSAT algorithm (which is basically the SAT algorithm with the outputs complemented), we get a True value. But we know that the boolean expression is satisfiable by setting (x1=1 and x2=1) and hence our algorithm is incorrect. That is why you can’t just take the output of an NP algorithm and reverse it with the expectation that it will work for Co-NP.