3-Satisfiability

Satisfiability's role as the first NP-complete problem implies that the problem is hard to solve in the worst case, but certain instances of the problem are not necessarily so tough. Suppose that each clause contains exactly one literal. To satisfy such a clause, we have to appropriately set that literal, so we can repeat this argument for every clause in the problem instance. Only when we have two clauses that directly contradict each other, such as , will the set not be satisfiable.  

Since clause sets with only one literal per clause are easy to satisfy, we are interested in slightly larger classes. Exactly what is the clause size at which the problem turns from polynomial to hard? This transition occurs when each clause contains three literals, the so-called 3-satisfiability problem, or 3-SAT:

Input: A collection of clauses C where each clause contains exactly 3 literals, over a set of Boolean variables V.

Output: Is there a truth assignment to V such that each clause is satisfied? Since this is a more restricted problem than satisfiablity, the hardness of 3-SAT implies that satisfiability is hard. The converse isn't true, as the hardness of general satisfiability might depend upon having long clauses. We can show the hardness of 3-SAT using a reduction that translates every instance of satisfiability into an instance of 3-SAT without changing the result of whether it is satisfiable.

This reduction transforms each clause independently based on its length, by adding new Boolean variables along the way. Suppose clause contained k literals:

• If k=1, meaning that , we create two new variables and four new 3-literal clauses: , , , . Note that the only way that all four of these clauses can be simultaneously satisfied is if , which must be the case if the original were to be satisfied.
• If k=2, meaning that , we create one new variable and two new clauses: , . Again, the only way to satisfy both of these clauses is to have at least one of and be true.
• If k=3, meaning that , we copy into the 3-SAT instance unchanged: .
• If k>3, meaning that , create n-3 new variables and n-2 new clauses in a chain, where for , , , and .

The most complicated case is that of the large clauses. If none of the original variables are , then there are not enough additional variables to be able to satisfy all of the new subclauses. You can satisfy by setting , but this forces , and so on until finally cannot be satisfied. But if any single literal , then we have n-3 free variables and n-3 remaining 3-clauses, so we can satisfy each of them.

This transform takes O(m+n) time if there were n clauses and m total literals in the SAT instance. Since any SAT solution also satisfies the 3-SAT instance and any 3-SAT solution sets the variables giving a SAT solution, the transformed problem is equivallent to the original.

Note that a slight modification to this construction would serve to prove that 4-SAT, 5-SAT, or any -SAT is also NP-complete. However, this construction breaks down when we try to use it for 2-SAT, since there is no way to stuff anything into the chain of clauses. It turns out that resolution gives a polynomial-time algorithm for 2-SAT, as discussed in Section .