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.


*

*cross-posted at cs.stackexchange.com.


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.
