# Showing a problem is in coNP

We have the problem $C = \{<G,S>| \text{ S is a minimal cover of G }\}$ and we want to show that $C\in coNP$.

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.

So is there another way to show that?

• I don't understand your suggested NP machine for the complement of $C$, how does it use $S$ from the input? – Ariel May 13 '17 at 13:57
• I think it will use S to check if it's minimal VC, if it is, return false, else return true, but I don't think it's the right approach. @Ariel – shinzou May 13 '17 at 14:28
• How do you check that a cover is minimal in polynomial time? (you haven't defined what a cover is and what being minimal means in this context, so you may be right that it's possible in your case) – Yuval Filmus May 13 '17 at 18:40

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.

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}$.

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

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}$.

This machine is polytime, and it accepts $\overline{C}$, showing that $\overline{C} \in \mathsf{NP}$, and so $C \in \mathsf{coNP}$.

• How does that prove $C\in coNP$? don't we need to show that for all witnesses the definition of C holds? – shinzou May 13 '17 at 18:07
• I described a witness for an instance of C to be a no instance, and showed that it always exists. That's how you show that a problem is in coNP. – Yuval Filmus May 13 '17 at 18:22
• What do you mean by the witness is "a no instance"? (PS I understand Hebrew so maybe I'll know the translation) – shinzou May 13 '17 at 18:25
• The instance is a no instance (a negative instance, an instance not belonging to the language), and the witness witnesses it. – Yuval Filmus May 13 '17 at 18:27
• So another way phrase this would be that there's a witness $w$ that represent a cover that is smaller than all other covers? – shinzou May 13 '17 at 18:36