0
$\begingroup$

How to prove that Set Cover can be polynomial-time reduced to CNF-SAT?

$\endgroup$
  • $\begingroup$ Proving that such a reduction exists should be doable using the fact that both problems are NP-complete. Or do you want to have an actual (nice) example of such a reduction? (and just out of curiosity, what would do you want to use it for?) $\endgroup$ – user53923 May 3 '17 at 9:47
  • 1
    $\begingroup$ see this Wikipedia page $\endgroup$ – D.W. May 3 '17 at 14:06
  • $\begingroup$ Prove that Set Cover is in NP, and then use Cook's theorem. (A direct reduction is also not too difficult, but why bother.) $\endgroup$ – Yuval Filmus May 3 '17 at 17:36
  • $\begingroup$ What is the direct reduction then? @YuvalFilmus $\endgroup$ – shinzou Jul 22 '17 at 19:44
  • $\begingroup$ @kuhaku You have variables for the sets, conditions that ensure that you cover all elements, and then you use "dynamic programming" to count how many sets you took, so you can enforce not taking too many. $\endgroup$ – Yuval Filmus Jul 23 '17 at 17:29

Your Answer

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

Browse other questions tagged or ask your own question.