Showing a problem is in coNP - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-17T20:50:50Z https://cs.stackexchange.com/feeds/question/75329 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/75329 1 Showing a problem is in coNP shinzou https://cs.stackexchange.com/users/43035 2017-05-13T13:03:43Z 2017-05-13T18:52:02Z <p>We have the problem $C = \{&lt;G,S&gt;| \text{ S is a minimal cover of G }\}$ and we want to show that $C\in coNP$.</p> <p>I can easily show that there's a ND TM that decides $coC$ using a guess to check if the drawn vertices are a minimal cover and if they are, return false. But it seems like it's wrong since this can be done with anything. </p> <p>So is there another way to show that?</p> https://cs.stackexchange.com/questions/75329/-/75334#75334 1 Answer by Yuval Filmus for Showing a problem is in coNP Yuval Filmus https://cs.stackexchange.com/users/683 2017-05-13T14:52:54Z 2017-05-13T18:52:02Z <p>Since coNP is confusing, let us construct an NP machine for $\overline{C}$. The input to the machine is a pair $\langle G,S \rangle$, where $S$ is a cover of $G$. The machine guesses another cover $T$, and verifies that $T$ is a cover of $G$ which is smaller than $S$. The cover $T$ is thus a witness to the fact that $S$ is not a cover of minimum size.</p> <p>If $S$ is not a minimal cover, then there exists some smaller cover $T$, and so the machine accepts the instance $\langle G,S \rangle$ if it guesses $T$. Conversely, if $S$ is a minimal cover, then no smaller cover exists, and so the machine rejects the instance $\langle G,S \rangle$ whatever the guess is. In total, the machine accepts the language $\overline{C}$.</p> <p>Here is a another way to look at things. We construct a machine that on input $\langle \langle G,S \rangle,T \rangle$, accepts if $S,T$ are covers of $G$, and $T$ is smaller than $S$. Then</p> <blockquote> <p>There exists $T$ such that the machine accepts $\langle \langle G,S \rangle,T \rangle$ if and only if $\langle G,S \rangle \in \overline{C}$.</p> </blockquote> <p>This machine is polytime, and it accepts $\overline{C}$, showing that $\overline{C} \in \mathsf{NP}$, and so $C \in \mathsf{coNP}$.</p>