34 1. Classical Computation
3-CNF is satisfied by the same values of x1,...,xn and appropriate values
of the auxiliary variables.
So our transformation (of a circuit into a 3-CNF) is indeed a reduction
of SAT to 3-SAT.
Here is another simple example of reduction.
ILP (integer linear programming). Given a system of linear inequalities
with integer coeﬃcients, is there an integer solution? (In other words, is the
In this problem the input is the coeﬃcient matrix and the vector of the
right-hand sides of the inequalities. It is not obvious that ILP ∈ NP. Indeed,
the solution might exist, but Merlin might not be able to communicate it to
Arthur because it is not immediately clear that the number of bits needed
to represent the solution is polynomial.
However, it is in fact true that, if a system of inequalities with integer
coeﬃcients has an integer solution, then it has an integer solution whose
binary representation has size bounded by a polynomial in the bit size of
the system; see [55, vol. 2, §17.1]. Therefore, ILP is in NP.
Now we reduce 3-SAT to ILP. Assume that a 3-CNF is given. We
construct a system of inequalities that has integer solutions if and only if
the 3-CNF is satisfiable. For each Boolean variable xi we consider an integer
variable pi. The negation ¬xi corresponds to the expression 1 − pi. Each
clause Xj ∨ Xk ∨ Xm (where X∗ are literals) corresponds to the inequality
Pj + Pk + Pm ≥ 1, where Pj,Pk,Pm are the expressions corresponding to
Xj,Xk,Xm. It remains to add the inequalities 0 ≤ pi ≤ 1 for all i, and
we get a system whose solutions are satisfying assignments for the given
Remark 3.5. If we do not require the solution to be integer-valued, we get
the standard linear programming problem. Polynomial algorithms for the
solution of this problem (due to Khachiyan and Karmarkar) are described,
e. g., in [55, vol. 1, §§13, 15.1].
An extensive list of NP-complete problems can be found in . Usually
NP-completeness is proved by some reduction. Here are several examples of
3-coloring. For a given graph G determine whether it admits a 3-
coloring. (By a 3-coloring we mean coloring of the vertices with 3 colors
such that each edge has endpoints of different colors.)
(It turns out that a similar 2-coloring problem can be solved in polyno-