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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ cross-posted at math.stackexchange.com/questions/142536/… $\endgroup$
    – user2346
    May 8, 2012 at 7:13
  • 1
    $\begingroup$ So in particular, the original reduction from SAT is not an answer to your question? (Please don't crosspost. If the question were not more ontopic here than on math.SE, I would close right away.) $\endgroup$
    – Raphael ♦
    May 8, 2012 at 8:43
  • $\begingroup$ @Raphael I found an answer.. Thanks for help anyway. I realized that SAT should be considered before 3-SAT as 3-SAT's NP-completeness can be known by reduction process from SAT. $\endgroup$
    – user2346
    May 8, 2012 at 8:57
  • $\begingroup$ @user2346 Got here just too late, apparently $\endgroup$
    – Lucas Cook
    May 8, 2012 at 9:00
  • 3
    $\begingroup$ Please do not post the same question on multiple Stack Exchange sites. $\endgroup$
    – Gilles 'SO- stop being evil'
    May 8, 2012 at 21:24

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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