# how do you prove that SAT is NP-complete?

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.

• cross-posted at math.stackexchange.com/questions/142536/… May 8, 2012 at 7:13
• 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.)
– Raphael
May 8, 2012 at 8:43
• @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. May 8, 2012 at 8:57
• @user2346 Got here just too late, apparently May 8, 2012 at 9:00
• Please do not post the same question on multiple Stack Exchange sites. May 8, 2012 at 21:24

## 1 Answer

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.

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