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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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