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 coefficients, is there an integer solution? (In other words, is the
system consistent?)
In this problem the input is the coefficient 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
coefficients 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.)
Previous Page Next Page