Using induction on k, how do I prove that the K-SAT problem is NP-complete?

On wikipedia, it describes the Cook-Levin theorem to prove that K-SAT is NPC by reducting the K-SAT problem to a circuit-SAT (which is reducible in polytime). But this does not use the induction method.

  • 1
    $\begingroup$ A proof is a proof, whether it uses induction or not. It's not clear why we'd care whether a proof uses induction or not. In any case: What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Dec 2 '19 at 5:20

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.