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

system consistent?)

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

3-CNF.

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 [28]. Usually

NP-completeness is proved by some reduction. Here are several examples of

NP-complete problems.

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-

mial time.)