A literal is a (negated) boolean variable, while a clause is disjunction of literals. A formula is in conjunctive normal form if it is a conjunction () of clauses. A subset of these are called 3cnf-formula if all the clauses have three literals. Define the following language
NP-Complete
Info
is NP-complete
It is known that SAT is NP-complete. Furthermore , thus . Given some boolean formula , this can be rewritten as a conjunction of disjunctions, by distributing and applying DeMorgan’s Law. Finally, a string of disjunctions can be decomposed into 3-length disjunctions by adding helper variables
Then is satisfied iff some choice of and satisfies the right. At most a constant factor of variables are introduced with this substitution. Thus can be made into a 3cnf-formula and is reduced to .