7
$\begingroup$

As it is, how do you prove that SAT is NP-complete?

I know what it means by NP-complete, so I do not need an explanation on that.

What I want to know is how do you know that one problem, such as SAT, is NP-complete without resorting to reduction to other problems such as hamiltonian problem or whatever.

$\endgroup$
15
$\begingroup$

I believe 3-SAT was originally reduced from the more general SATISFIABILITY in Karp's paper that outlined 21 NP-complete problems.

Wikipedia has a description of how to show that SATISFIABILITY is NP-complete, a result that's known as the Cook-Levin theorem. The idea of this proof is to show that any polynomial time nondeterministic Turing machine can be modeled as a boolean expression with polynomial size. The boolean expression has terms to represent the valid configuration space of the Turing machine: where the tape head is, what the current state is, what symbols are written on the tape, and what transitions are valid at every position. Because the NTM will halt in polynomial time, the configuration space is bounded and we can make a (large) polynomial expression to represent it.

$\endgroup$
  • 9
    $\begingroup$ How fitting that a Cook should give this answer. $\endgroup$ – Raphael May 10 '12 at 15:13
  • $\begingroup$ @Raphael Heh, no relation (as far as I know!) $\endgroup$ – Lucas Cook May 10 '12 at 23:39
  • $\begingroup$ 3SAT is already in Steve Cook's original paper. $\endgroup$ – Kaveh Jun 30 '13 at 5:29

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.