Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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