Npcompleteness Proofs
NPcompleteness proofs: The NPcompleteness of the circuitsatisfiability problem relies on a direct proof that L ≤_{P} CIRCUITSAT for every language L ∈ NP. In this section, we shall show how to prove that languages are NPcomplete without directly reducing every language in NP to the given language. We shall illustrate this methodology by proving that various formulasatisfiability problems are NPcomplete. NPcomplete problems provides many more examples of the methodology. In other words, by reducing a known NPcomplete language L′ to L, we implicitly reduce every language in NP to L. Thus,

Prove L ∈ NP.

Select a known NPcomplete language L′.

Describe an algorithm that computes a function f mapping every instance x ∈ {0, 1}* of L′ to an instance f(x) of L.

Prove that the function f satisfies x ∈ L′ if and only if f (x) ∈ L for all x ∈ {0, 1}*.

Prove that the algorithm computing f runs in polynomial time.
(Steps 25 show that L is NPhard.) This methodology of reducing from a single known NPcomplete language is far simpler than the more complicated process of showing directly how to reduce from every language in NP. Proving CIRCUITSAT ∈ NPC has given us a "foot in the door." Knowing that the circuitsatisfiability problem is NPcomplete now allows us to prove much more easily that other problems are NPcomplete. Moreover, as we develop a catalog of known NPcomplete problems, we will have more and more choices for languages from which to reduce.
Formula satisfiability: We illustrate the reduction methodology by giving an NPcompleteness proof for the problem of determining whether a boolean formula, not a circuit, is satisfiable. This problem has the historical honor of being the first problem ever shown to be NPcomplete.
We formulate the (formula) satisfiability problem in terms of the language SAT as follows. An instance of SAT is a boolean formula φ composed of

n boolean variables: x_{1}, x_{2}, ..., x_{n};

m boolean connectives: any boolean function with one or two inputs and one output, such as ∨ (AND), ∧ (OR), ¬ (NOT), → (implication), ↔ (if and only if); and

parentheses. (Without loss of generality, we assume that there are no redundant parentheses, i.e., there is at most one pair of parentheses per boolean connective.)
It is easy to encode a boolean formula φ in a length that is polynomial in n m. As in boolean combinational circuits, a truth assignment for a boolean formula φ is a set of values for the variables of φ, and a satisfying assignment is a truth assignment that causes it to evaluate to 1. A formula with a satisfying assignment is a satisfiable formula. The satisfiability problem asks whether a given boolean formula is satisfiable; in formallanguage terms,
SAT = {〈φ〉 : φ is a satisfiable boolean formula}.
As an example, the formula
φ = ((x_{1} → x_{2}) ∧ ¬((¬x_{1} ↔ x_{3}) ∨ x_{4})) ∨ ¬x_{2}
has the satisfying assignment 〈x_{1} = 0, x_{2} = 0, x_{3} = 1, x_{4} = 1〉, since
and thus this formula φ belongs to SAT.
The naive algorithm to determine whether an arbitrary boolean formula is satisfiable does not run in polynomial time. There are 2^{n} possible assignments in a formula φ with n variables. If the length of 〈φ〉 is polynomial in n, then checking every assignment requires Ω(2^{n}) time, which is superpolynomial in the length of 〈φ〉. As the following theorem shows, a polynomialtime algorithm is unlikely to exist.
3CNF satisfiability: Many problems can be proved NPcomplete by reduction from formula satisfiability. The reduction algorithm must handle any input formula, though, and this requirement can lead to a huge number of cases that must be considered. It is often desirable, therefore, to reduce from a restricted language of boolean formulas, so that fewer cases need be considered. Of course, we must not restrict the language so much that it becomes polynomialtime solvable. One convenient language is 3CNF satisfiability, or 3CNFSAT.
We define 3CNF satisfiability using the following terms. A literal in a boolean formula is an occurrence of a variable or its negation. A boolean formula is in conjunctive normal form, or CNF, if it is expressed as an AND of clauses, each of which is the OR of one or more literals. A boolean formula is in 3conjunctive normal form, or 3CNF, if each clause has exactly three distinct literals.
For example, the boolean formula
(x_{1} ∨ ¬x_{1} ∨ ¬x_{2}) ∧ (x_{3} ∨ x_{2} ∨ x_{4}) ∧ (¬x_{1} ∨ ¬x_{3} ∨ ¬x_{4})
is in 3CNF. The first of its three clauses is (x_{1} ∨ ¬x_{1} ∨ ¬x_{2}), which contains the three literals x_{1}, ¬x_{1}, and ¬x_{2}.
In 3CNFSAT, we are asked whether a given boolean formula φ in 3CNF is satisfiable. The following theorem shows that a polynomialtime algorithm that can determine the satisfiability of boolean formulas is unlikely to exist, even when they are expressed in this simple normal form.