# What is the Certificate for Set Cover?

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?

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.
• @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. – David Richerby Nov 10 '14 at 11:48
• @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. – D.W. Nov 10 '14 at 15:37