Flaw in my NP = CoNP Proof?

Question

I have this very simple "proof" for NP = CoNP and I think I did something wrongly somewhere, but I cannot find what is wrong. Can someone help me out?

Let A be some problem in NP, and let M be the decider for A. Let B be the complement, i.e. B is in CoNP. Since M is a decider, you can use it to decide B as well (just flip the answer). Doesn't that mean that we solve both NP and CoNP problems with the same M?

To put it more concretely.

Let A be some NP-complete problem, and let M be decider for A. Consider any problem B in CoNP. We consider its complement not-B, which is in NP, and then get a polynomial reduction to A. Then we run our decider M and flip our answer. We thus obtain a decider for B. This implies B is in NP as well.

May I know what is wrong with my reasoning?

Answer 1

There are two possible bugs in this proof:

1. When you say "decider" - you mean a deterministic TM. In this case, the best translation (to our knowledge) from an NP machine to a deterministic machine may yield a machine that runs in exponential time, so after complementing you will have a decider for the complement in exponential time, proving that $co-NP\subseteq EXP$ (or, after some optimization, $co-NP\subseteq PSPACE$).

2. When you say "decider" you mean a nondeterministic TM. In this case, flipping the answer will not necessarily complement the language. Indeed, the language of the flipped machine will be all the words for which there exists a rejecting run of $M$ on $w$

Answer 2

Here's another way of looking at the point that Shaull makes with respect to "deciders".

A problem is in NP if and only if there is an algorithm $V: \{0,1\}^n \times \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}$ such that

• for every YES instance $x \in \{0,1\}^n$, there is a certificate $p \in \{0,1\}^{\mathrm{poly}(n)}$ such that $V(x,p) = 1$; and

• for every NO instance $x \in \{0,1\}^n$, we have $V(x,p) = 0$ for all $p \in \{0,1\}^{\mathrm{poly}(n)}$.

These are usually described as the completeness and soundness conditions for the NP verification algorithm: the "completeness" condition says that every YES instance has a certificate, and the "soundness" condition says that the algorithm is never fooled by a NO instance. For coNP it's the other way around: there is a verifier algorithm which will accept at least one certificate for any NO instance, but which can never be fooled by a YES instance.

If you want to show that NP ⊆ coNP, you have to show that every NP problem has a coNP-type verifier, which can certify NO instances instead of YES instances. You cannot do this with a nondeterministic Turing machine: there's no way that we know of, for instance, to efficiently map instances of SAT to one another, in such a way that all unsatisfiable formulae are mapped to satisfiable ones, and vice versa. (Negating the output ofr the formula isn't enough, for example: a formula which is satisfiable but not a tautology would just get mapped to a different formula which was satisfiable but not a tautology, when we would require an unsatisfiable formula instead.) There is simply no way that we know of to 'fool' a nondeterministic machine into detecting anything like all of its paths being rejecting paths.

You might ask: "Doesn't the nondeterministic Turing machine know what result it gets?" The answer would be no, it doesn't. The working of the non-deterministic machine doesn't give it access to any information about more than one computational path at once: you might think of it working in many paths in parallel, but within each path it only knows about that one path. If you try to equip it with the ability to "realize" whether or not there are any solutions as some point, you are instead describing a machine with an NP oracle, which is more (potentially!) powerful than a simple nondeterministic Turing machine.

• For instance, if you equip a (deterministic) Turing machine with an NP oracle, then the problems which can be solved in polynomial time on that machine is called $\Delta_2^{\mathrm P}$, which is often written $\mathsf{P}^{\mathsf{NP}}$. The "oracle" allows the machine to simply recieve answers to NP-complete problems in a single step, and so $\mathsf{P}^{\mathsf{NP}}$ obviously contains P; and because you can negate answers, it also obviously contains coNP. But we don't know whether the reverse containments hold, exactly because we don't know how to trick nondeterministic Turing machines into detecting NO answers.

• What's more, if you give a nondeterministic Turing machine the ability to come to a realisation about the outcome of a problem in NP, the problems which that machine can solve in polynomial time is called $\Sigma_2^{\mathrm P}$, or $\mathsf{NP}^{\mathsf{NP}}$, and this is widely believed to be strictly larger than the class $\mathsf{P}^{\mathsf{NP}}$. This also contains both NP and coNP — but like NP, it isn't known to be closed under complements: the nondeterministic oracle machine might be able to know when a problem in NP has a NO answer because of the oracle, but it would still be stuck to operating within one of its own (quite powerful) computational branches, so that it would not be able to tell if all of its own computational branches were rejecting.

If you keep on supplying the machine with more powerful oracles for solving problems in $\mathsf{NP}$, $\mathsf{NP}^{\mathsf{NP}}$, and so forth, you end up defining the classes of the polynomial hierarchy, which are thought to be all distinct from one another from the first level onwards.

So, no, there's no machine (deterministic or otherwise) which can simply 'decide' that a problem is a YES or NO instance efficiently, unless we use oracles; but even with such an oracle, we end up with a machine which is (probably) more powerful than either NP or coNP, not one which shows that they're equal.

Answer 3

Your reasoning implies that RE=coRE, but this is provably false. You could try to figure out a proof of that and then see where your reduction fails.

Recall that RE is the complexity class of recursively enumerable languages, which are languages of the form $\{ x : P \text{ halts on input } x \}$. You can also think of it in non-deterministic terms: RE is the class of languages of the form $\{ x : (x,w) \in L' \text{ for some } w \}$, where $L'$ is recursive (computable).

Here is a proof that both definitions match. Suppose first $L = \{ x : p \text{ halts on input } x \}$. Let $L' = \{ (x,w) : p \text{ halts on input } x \text{ in } w \text{ steps} \}$. The language $L'$ is recursive and $L = \{ x : (x,w) \in L' \text{ for some } w \}$.

For the other direction, let $L = \{ x : (x,w) \in L' \text{ for some } w \}$, where $L'$ is recursive, say computed by the program $P(x,w)$. We construct a new program $Q(x)$ which enumerates all possible $w$ and runs $P(x,w)$ on all $w$, in order. If $P(x,w)$ ever accepts for some $w$, then $Q$ halts. It's not hard to check that $L = \{ x : Q \text{ halts on input } x \}$.

For your convenience, here are outlines for a proof that RE is different from coRE. The language $L = \{(P,x) : P \text{ halts on input x}\}$ is clearly recursively enumerable: a program for it simply runs $P$ on $x$. Suppose there was a program $H$ such that $H(P,x)$ halts if and only if $(P,x) \notin L$. We define a new program $G$ by $G(x)=H(x,x)$. Is $(G,G) \in L$? If so, then $G$ halts on $G$, so $H$ halts on $(G,G)$, so $(G,G) \notin L$. If $(G,G) \notin L$, then $G$ doesn't halt on $G$, so $H$ doesn't halt on $(G,G)$, so $(G,G) \in L$. This contradiction shows that $H$ cannot exist.

Now try to run your proof in this case and see what goes wrong. In more detail, try to construct the program $H$ using your recipe, and follow the proof - at some point something wouldn't be quite right.

Answer 4

Here's a TL;DR version; I've also posted a longer answer to a similar question.

Suppose we have a language $A$ that's decided in polynomial time by nondeterministic Turing machine $M$. The point is that $x\in A$ iff there $M$ has some accepting path on input $x$. However, since $M$ is nondeterministic, there may also be rejecting paths when it runs on $x$. If you just reverse the accepting and rejecting states, you'll go from a machine that had some accepting paths and some rejecting ones to a machine that has some rejecting paths and some accepting ones. In other words, it still has accepting paths, so it still accepts. Flipping the accept and reject states of a nondeterministic machine does not, in general, cause you to accept the complement language.

It is this asymmetry of definition (accept if any path accepts; reject only if all paths reject) that makes the NP vs co-NP problem difficult.

Answer 5

I actually agree that your nondeterministic machine M can decide whether a given input string is in B. However, it "decides" slightly differently than the way it decides if a given input is in A. In the latter case, it does so by (nondeterministically) finding an accepting state. In the former case, it does so by failing to find any accepting states. Why does this difference matter? Let's see:

When asking M "Is the string in the language A?"

M reaches an accept state. This, you can prove (see, for example, the Sipser book theorem 7.20) implies that there is a deterministic machine that verifies the string is in A in polynomial time

When asking M "Is the string in the language B?"

M reaches reject states on all branches of its nondeterministic computation. If you think about how the verifier proof above works, you will see that it cannot be accomplished in this situation. This is roughly because the verifier uses the path that M takes through its state space as "proof". In this case, there is no one such path.

Conclusion:

If you consider the existence of a polynomial time deterministic verifier for a language to be the definition of an NP language (which you should), the existence of M does not prove that B is in NP.