Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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":
3-SAT is NP-Complete because SAT is - any SAT formula can be rewritten as a conjunctive statement of literal clauses with 3 literals, and the satisifiability of the new statement will be identical to that of the original formula.
The basic observation is that in a conjunctive statement (AND-of-OR clauses), you can introduce a new literal if you also introduce its negation in another clause. Since the new literal will be false in either one or the other clause whatever its value may be, the satisfiability of the extended statement will remain the same as the original statement.
Looking at any SAT formula as split into conjunctive clauses (chop it up at the ANDs), we need to cover cases for 1, 2, 3, and more-than-3 literals per clause. I'll denote (and, or, not) as (&,|,~) for brevity, use lowercase letters for literal terms from the original formula, and uppercase ones for those that are introduced by rewriting it. (A literal can obviously hold the place of either a variable or its negation.)
Single-literal clauses: Introduce 2 literals and cover the conjunction of all their combinations, to make sure at least one of these clauses is false if the original literal is. (a) becomes (a|A|B) & (a|A|~B) & (a|~A|B) & (a|~A|~B)
2-literal clauses: Introduce 1 variable, and cover both its possible values. (a|b) becomes (a|b|A) & (a|b|~A)
3-literal clauses: These are already in 3-SAT friendly form (a|b|c)
More-than-three literal clauses: Split the literals into the first and the last pair, and work on all the single ones in between - as an example, (a|b|c|...|y|z) becomes (a|b|A) & (~A|c|B) & (~B|d|C) & ... and so on ...& (~V|x|W) & (~W|y|z)
Rewriting like this, the growth in the number of variables is at worst 2 new literals for every original one, and the growth in the length of the statement is at worst 4 clauses for every original literal, which means that this transformation can be carried out with a polynomial amount of work in terms of the original problem size.
All in all, it means that we have a deterministic polynomial-time method for turning SAT problems into 3-SAT problems, so if we also had a deterministic polynomial-time algorithm for 3-SAT, we could do one after the other and solve SAT in deterministic polynomial time this way.
This establishes that 3-SAT is NP-Hard ("at least as difficult as anything in NP"), to make it NP-Complete, we must show that it is also itself a member of the class NP. This amounts to finding a polynomial-time algorithm to verify proposed evidence that the formula is satisfiable: given a set of values for all the literals that supposedly satisfy the formula, just put them in and evaluate if it's true. A non-deterministic machine would be capable of producing such an assignment in polynomial time, so as long as we can demonstrate that a solution can be verified in polynomial time, that's a wrap, and 3-SAT is in NPC.
This whole proof construction method of Reduce known NPC problem to your problem, to prove its NP-hardness Show deterministic polynomial-time verification of a solution rests on the Cook-Levin theorem that NP machines correspond to SAT formula
