Hardness of Set Cover

Now we have one NP-complete problem.

Can prove set cover is no easier by showing how an algorithm for set cover could be used to solve SAT.

How can we determine satisfiabilty with a polynomial number of calls to an algorithm for set cover?

• First, augment the formula with a clause for all n variables (contains positive and negative literal).
• Now, each clause becomes something to be covered (a ``minority group'').
• Each literal (positive or negative variable) becomes a potential committee member that ``covers'' the clauses that it appears in.
• Problem has a size n cover if and only if formula is satisfiable.

Example...