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?

  • $\begingroup$ I don't understand your suggested NP machine for the complement of $C$, how does it use $S$ from the input? $\endgroup$
    – Ariel
    Commented May 13, 2017 at 13:57
  • $\begingroup$ 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 $\endgroup$
    – shinzou
    Commented May 13, 2017 at 14:28
  • $\begingroup$ 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) $\endgroup$ Commented May 13, 2017 at 18:40

1 Answer 1


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

  • $\begingroup$ How does that prove $C\in coNP$? don't we need to show that for all witnesses the definition of C holds? $\endgroup$
    – shinzou
    Commented May 13, 2017 at 18:07
  • $\begingroup$ 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. $\endgroup$ Commented May 13, 2017 at 18:22
  • $\begingroup$ What do you mean by the witness is "a no instance"? (PS I understand Hebrew so maybe I'll know the translation) $\endgroup$
    – shinzou
    Commented May 13, 2017 at 18:25
  • $\begingroup$ The instance is a no instance (a negative instance, an instance not belonging to the language), and the witness witnesses it. $\endgroup$ Commented May 13, 2017 at 18:27
  • $\begingroup$ So another way phrase this would be that there's a witness $w$ that represent a cover that is smaller than all other covers? $\endgroup$
    – shinzou
    Commented May 13, 2017 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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