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

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.

-

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

-
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.