12
$\begingroup$

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?

$\endgroup$

migrated from cstheory.stackexchange.com Mar 12 '13 at 16:20

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

  • 2
    $\begingroup$ As the answers below explain at length, you are not using the notion of "decider" correctly. Problems in coNP are not those with a "flipped NP decider". There is an important assymmetry in NP problems between accepting an input ("there are non-deterministic choices which lead to accepting") and rejecting it ("all non-deterministic choices lead to rejecting"). Your argument presupposes that for NP rejecting a string means ("there are a non-determinstic choices which lead to rejection"), and that is the flaw. In other words, you got your quantifiers mixed up. $\endgroup$ – Andrej Bauer Mar 13 '13 at 14:32
  • 1
    $\begingroup$ You might find the answers to this question enlightening. $\endgroup$ – Raphael Mar 13 '13 at 14:38
  • $\begingroup$ @Raphael Surprisingly, that question doesn't mention co-NP at all! (Though I agree that it's a useful read for somebody who's unsure about this kind of thing.) $\endgroup$ – David Richerby Jan 31 '18 at 15:33
  • $\begingroup$ @DavidRicherby Since the answer is, basically, "use the definition of NP instead of flawed intuition", I would hope so! $\endgroup$ – Raphael Jan 31 '18 at 15:44
  • 1
    $\begingroup$ Rule of thumb: the "flip final states" construction only works for determinstic models. Study how it fails for NFA to understand why. See also here and here. $\endgroup$ – Raphael Jan 31 '18 at 16:34
2
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The existence of $M$ doesn't prove that $B$ is in NP precisely because you have to use this "weird" acceptance criterion to make it "accept" $B$. NP is defined via the conventional nondeterministic acceptance criterion. (The acceptance criterion is slightly weird partly because the question talks about flipping accepting and rejecting states in $M$ but you don't seem to have done that.) $\endgroup$ – David Richerby Oct 5 '14 at 8:18
6
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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 NPcoNP, 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.

$\endgroup$
  • $\begingroup$ Hi, thank you to you and Shauli for the comments. Are you saying that a NTM can recognize an NP language in polytime, but cannot decid a NP language in polytime? I think that is what I am assuming when I say that I have a decider for NP problems. $\endgroup$ – simpleton Mar 12 '13 at 19:54
  • 2
    $\begingroup$ Oh, I think I sort of get what you mean. Are you saying that I am using oracle reduction, and that actually shows that the problem is in $P^{NP}$ (which is true because $NP \subset P^{NP}$ and $CoNP \subset P^{NP}$)? The oracle reduction shows that UNSAT is NP-hard, but I still need to show that $UNSAT \in NP$, and I cannot show that? $\endgroup$ – simpleton Mar 12 '13 at 20:25
  • 5
    $\begingroup$ NP-hardness is defined with many-one reductions, not oracle reductions. $\endgroup$ – Yuval Filmus Mar 13 '13 at 5:57
16
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I'm not sure why that matters. My definition of a decider is that I accept if input is in L and reject if input is not in L. This decider can be deterministic or non-deterministic. However, I say that L is in NP, and therefore if I am using a non-deterministic TM then I will take polynomial time. Also, may I know why flipping the bit does not necessarily complement the language. To my knowledge CoNP = {L | not L \in NP}. Therefore, if I flip the bit I should obtain the answer? $\endgroup$ – simpleton Mar 12 '13 at 10:03
  • $\begingroup$ Let $L\in NP$. Consider a nondeterministic TM that works as follows - in one run, it always outputs "reject". In other runs, it recognizes $L$ in polynomial time (possible since $L\in NP$). Consider what happens if you flip the bit - the rejecting run becomes accepting for every input, so the complemented machine recognizes $\Sigma^*$ - which is not the complement unless $L=\emptyset$. I suggest you review closely the definitions of nondeterminism to understand this fully. $\endgroup$ – Shaull Mar 12 '13 at 10:10
  • $\begingroup$ I do not mean that I flip the bit of every single computation path. What I mean is that if my TM accepts, then this means that there exists a computation path that reaches an accept state. This means L is in NP, which means the complement is in coNP. If my TM rejects, then this means the every computational path rejects. This means that the complement is in NP, which means L is in CoNP. $\endgroup$ – simpleton Mar 12 '13 at 10:19
  • 4
    $\begingroup$ @simpleton: You know that an NTM does not have access to all paths at once, only one path? You think as someone who deterministically analyzes the behaviour of the NTM from the outside. $\endgroup$ – frafl Mar 12 '13 at 11:43
  • 7
    $\begingroup$ I think the OP could benefit from looking up the definition of NP more carefully. $\endgroup$ – MCH Mar 12 '13 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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