Flaw in my NP = CoNP Proof? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-19T21:04:01Z https://cs.stackexchange.com/feeds/question/10485 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/10485 12 Flaw in my NP = CoNP Proof? simpleton https://cs.stackexchange.com/users/7253 2013-03-12T09:52:11Z 2018-01-31T15:49:11Z <p>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?</p> <p>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?</p> <p>To put it more concretely.</p> <p>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. </p> <p>May I know what is wrong with my reasoning?</p> https://cs.stackexchange.com/questions/10485/-/10486#10486 16 Answer by Shaull for Flaw in my NP = CoNP Proof? Shaull https://cs.stackexchange.com/users/6890 2013-03-12T09:57:35Z 2013-03-12T17:22:12Z <p>There are two possible bugs in this proof:</p> <ol> <li><p>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$).</p></li> <li><p>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 <em>there exists</em> a rejecting run of $M$ on $w$</p></li> </ol> https://cs.stackexchange.com/questions/10485/-/10492#10492 14 Answer by Niel de Beaudrap for Flaw in my NP = CoNP Proof? Niel de Beaudrap https://cs.stackexchange.com/users/2152 2013-03-12T17:44:17Z 2013-03-12T17:44:17Z <p>Here's another way of looking at the point that Shaull makes with respect to "deciders".</p> <p>A problem is in <strong>NP</strong> if and only if there is an algorithm $V: \{0,1\}^n \times \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}$ such that</p> <ul> <li><p>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</p></li> <li><p>for every NO instance $x \in \{0,1\}^n$, we have $V(x,p) = 0$ for all $p \in \{0,1\}^{\mathrm{poly}(n)}$.</p></li> </ul> <p>These are usually described as the <em>completeness</em> and <em>soundness</em> conditions for the <strong>NP</strong> verification algorithm: the "completeness" condition says that <em>every</em> YES instance has a certificate, and the "soundness" condition says that the algorithm is never fooled by a NO instance. For <strong>coNP</strong> 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.</p> <p>If you want to show that <strong>NP</strong> &sube; <strong>coNP</strong>, you have to show that every <strong>NP</strong> problem has a <strong>coNP</strong>-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 <em>all</em> unsatisfiable formulae are mapped to satisfiable ones, <em>and vice versa</em>. (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.</p> <p>You might ask: "Doesn't the nondeterministic Turing machine <em>know</em> what result it gets?" The answer would be <em>no</em>, 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 <em>with an</em> <strong>NP</strong> <em>oracle</em>, which is more (potentially!) powerful than a simple nondeterministic Turing machine.</p> <ul> <li><p>For instance, if you equip a (deterministic) Turing machine with an <strong>NP</strong> 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 <strong>NP</strong>-complete problems in a single step, and so $\mathsf{P}^{\mathsf{NP}}$ obviously contains <strong>P</strong>; and because you can negate answers, it also obviously contains <strong>coNP</strong>. 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.</p></li> <li><p>What's more, if you give a <em>nondeterministic</em> Turing machine the ability to come to a realisation about the outcome of a problem in <strong>NP</strong>, the problems which <em>that</em> 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 <strong>NP</strong> and <strong>coNP</strong> &mdash; but like <strong>NP</strong>, it isn't known to be closed under complements: the nondeterministic oracle machine might be able to know when a problem in <strong>NP</strong> has a NO answer because of the oracle, but it would still be stuck to operating within one of <em>its own</em> (quite powerful) computational branches, so that it would not be able to tell if all of <em>its own</em> computational branches were rejecting.</p></li> </ul> <p>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 <a href="http://en.wikipedia.org/wiki/Polynomial_hierarchy">polynomial hierarchy</a>, which are thought to be all distinct from one another from the first level onwards.</p> <p>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) <em>more</em> powerful than either <strong>NP</strong> or <strong>coNP</strong>, not one which shows that they're equal.</p> https://cs.stackexchange.com/questions/10485/-/10506#10506 6 Answer by Yuval Filmus for Flaw in my NP = CoNP Proof? Yuval Filmus https://cs.stackexchange.com/users/683 2013-03-13T05:56:39Z 2013-03-13T05:56:39Z <p>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.</p> <p>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).</p> <p>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 \}$.</p> <p>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 \}$.</p> <p>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.</p> <p>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.</p> https://cs.stackexchange.com/questions/10485/-/30605#30605 -2 Answer by Alex for Flaw in my NP = CoNP Proof? Alex https://cs.stackexchange.com/users/22376 2014-10-05T05:44:00Z 2014-10-05T06:00:19Z <p>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:</p> <h2>When asking M "Is the string in the language A?"</h2> <p>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</p> <h2>When asking M "Is the string in the language B?"</h2> <p>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.</p> <h2>Conclusion:</h2> <p>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. </p> https://cs.stackexchange.com/questions/10485/-/87565#87565 2 Answer by David Richerby for Flaw in my NP = CoNP Proof? David Richerby https://cs.stackexchange.com/users/9550 2018-01-31T15:38:29Z 2018-01-31T15:49:11Z <p>Here's a TL;DR version; I've also posted a <a href="https://cs.stackexchange.com/a/21618/9550">longer answer</a> to a similar question.</p> <p>Suppose we have a language $A$ that's decided in polynomial time by nondeterministic Turing machine&nbsp;$M$. The point is that $x\in A$ iff there $M$&nbsp;has <em>some</em> accepting path on input&nbsp;$x$. However, since $M$&nbsp;is nondeterministic, there may also be rejecting paths when it runs on&nbsp;$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.</p> <p>It is this asymmetry of definition (accept if <em>any</em> path accepts; reject only if <em>all</em> paths reject) that makes the <strong>NP</strong> vs <strong>co-NP</strong> problem difficult.</p>