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

Question

As it is, how do you prove that 3-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 3-SAT, is NP-complete without resorting to reduction to other problems such as hamiltonian problem or whatever.

• cross-posted at cs.stackexchange.com.

Answer 1

Theorem 2 of Cook's paper that launched the field of NP-completeness showed that 3-SAT (there called $D_3$) is as hard as SAT. Theorem 1 demonstrated, without performing any reduction to other problems, that SAT is NP-complete. If you allow reference to SAT, this answers the question.

TeX version of Cook's paper "The Complexity of Theorem Proving Procedures":

http://4mhz.de/cook.html

Answer 2

This is done by a simple reduction from SAT. Note that general CNF clause $(\alpha_1\vee \alpha_2\vee\dots \alpha_n)$ can be transformed into the sequence of clauses $(\alpha_1\vee\alpha_2\vee y_1)\wedge(\overline{y_1}\vee \alpha_3 \vee y_2) \wedge\dots\wedge (\overline{y_{n-3}}\vee \alpha_{n-1}\vee\alpha_n)$, with the $y_1,\dots,y_{n-3}$ being new variables.

Now, the original clause is satisfied iff the same assignment to the original variables can be augmented by an assignment to the new variables that satisfies the sequence of clauses. I'll let you work out the details.