Consider the set cover problem: given a collection of sets ${\cal U}$ whose elements come from $\{1, \ldots, m\}$ find the smallest number of sets in ${\cal U}$ whose union is all of $\{1, \ldots, m\}$. My question is: what would be a certificate for this problem? That is, if I wanted to convince someone that it is not possible to do this with fewer than $k$ sets, what information could I provide that would allow someone to verify that this is the case in polynomial time?


1 Answer 1


The set cover is not a decision problem, so it doesn't necessarily have a certificate. Rather, it is an optimization problem.

To make it a problem in NP (a decision problem, with a certificate), you need to apply the standard trick to convert an optimization problem to a decision problem: introduce a budget. Thus, the decision budget is: given a collection of sets and an integer $k$, determine whether there exists a subset of $\le k$ sets whose union is all of $\{1,\dots,m\}$. That is a decision procedure, and does have a certificate: the subset of size $k$ is the certificate.

See also Optimization version of decision problems and standard textbooks.

  • $\begingroup$ Thank you! I notice you said "doesn't necessarily" have a certificate. So is it nevertheless possible that set cover (the optimization version of it, that is) does have a certificate? $\endgroup$
    – Pete V.
    Commented Nov 9, 2014 at 18:00
  • 3
    $\begingroup$ @PeteV., There's no certificate for it, unless NP = co-NP (which is unlikely)... I think. $\endgroup$
    – D.W.
    Commented Nov 9, 2014 at 19:01
  • $\begingroup$ @D.W. That seems reasonable. Certainly, if NP=co-NP, there is a certificate: a cover of size $m$ plus a certificate that there is no cover of size $m-1$. Though, of course, your claim is the converse. $\endgroup$ Commented Nov 10, 2014 at 11:48
  • 1
    $\begingroup$ @DavidRicherby, here's my reasoning. Consider the decision problem "Does this family of sets have a set cover using $\le k$ sets?". This is in NP. If we had a certificate for Pete V.'s optimization problem, we could use it as a certificate to prove the answer to this decision problem is "no". That means this decision problem is in co-NP. But this decision problem is NP-complete. If a NP-complete problem is in co-NP, then NP = co-NP. $\endgroup$
    – D.W.
    Commented Nov 10, 2014 at 15:37

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.