3
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\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. Nov 9 '14 at 18:00
  • 3
    $\begingroup$ @PeteV., There's no certificate for it, unless NP = co-NP (which is unlikely)... I think. $\endgroup$ – D.W. Nov 9 '14 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$ – David Richerby Nov 10 '14 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. Nov 10 '14 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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