Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Chapter 2

NP-Completeness

Nor has there been agreement about the right road to truth.

—Isaiah Berlin

The notions of reducibility and completeness play an important role in the classification of the complexity of problems from diverse areas of applications. In this chapter, we formally define two types of reducibilities: the polynomial-time many-one reducibility and the polynomial-time Turing reducibility. Then we prove several basic NP-complete problems and discuss the complexity of some combinatorial optimization problems.

2.1 NP

The complexity class NP has a nice characterization in terms of class P and polynomial length-bounded existential quantifiers.

Theorem 2.1

Proof

Let $c02-math-0008$ where $c02-math-0009$ is a one-tape NTM with a polynomial-time bound p(n). Similar to Theorem 1.9, we regard Δ as a multivalued function from $c02-math-0012$ to $c02-math-0013$ , and let k be the maximum number of values that Δ can assume on some $c02-math-0016$ . Let $c02-math-0017$ be k new symbols not in Γ. We define a DTM M^∗ over the strings $c02-math-0021$ , where $c02-math-0022$ and $c02-math-0023$ . The DTM M^∗ is similar to the third step of the machine M₁ of Theorem 1.9. Namely, on input $c02-math-0026$ , where $c02-math-0027$ , M^∗ simulates M on input x for at most m moves. At the jth move, M^∗ reads the jth symbol $c02-math-0035$ of y and follows the i_jth value of the multivalued function Δ. M^∗ accepts the input $c02-math-0040$ if and only if this simulation accepts in m moves. It is clear that $c02-math-0042$ if and only if $c02-math-0043$ for some $c02-math-0044$ of length $c02-math-0045$ .

Conversely, if A can be represented by set B and function p as in (2.1), then we can design a three-tape NTM M for A as follows: on input x, M first makes $c02-math-0053$ nondeterministic moves to write down a string y of length $c02-math-0055$ on tape 2. Then, it copies $c02-math-0056$ to tape 3 and simulates the DTM M_B for B on tape 3. It accepts if M_B accepts $c02-math-0060$ . It is clear that M accepts the set A.

Based on the above characterization, we often say a nondeterministic computation is a guess-and-verify computation. That is, if set A has the property (2.1), then for any input x, an NTM M can determine whether $c02-math-0066$ by firstguessing a string y of length $c02-math-0068$ and then deterministically verifying that $c02-math-0069$ , in time polynomial in $c02-math-0070$ . For each $c02-math-0071$ , a string y of length $c02-math-0073$ such that $c02-math-0074$ is called a witness or a certificate for x. This notion of guess-and-check computation is a simple way of presenting a nondeterministic algorithm.

In the following text, we introduce some well-known problems in NP. We define each problem Π in the form of a decision problem: “Given an input instance x, determine whether it satisfies the property $c02-math-0078$ .” Each problem Π has a corresponding language $c02-math-0080$ . We say that Π is in NP to mean that the corresponding language L_Π is in NP.

Example 2.2

Example 2.3

(HAMILTONIAN CIRCUIT). We first review the terminology of graphs. A graph is an ordered pair of disjoint sets (V,E) such that $c02-math-0099$ and E is a set of pairs of elements in V. The set V is the set of vertices, and the set E is the set of edges. Two vertices are adjacent if there is an edge between them. A path is a sequence of vertices of which any two consecutive vertices are adjacent. A path is simple if all its vertices are distinct. A cycle is a path that is simple except that the first and the last vertices are identical.

Let $c02-math-0104$ be the vertex set of a graph $c02-math-0105$ . Then its adjacency matrix is an $c02-math-0106$ matrix $c02-math-0107$ defined by

Note that $c02-math-0109$ and $c02-math-0110$ . So, we have only $c02-math-0111$ independent variables in an $c02-math-0112$ adjacency matrix, for example, x_ij, $c02-math-0114$ . We use the string $c02-math-0115$ to encode the graph G.

The problem HAMILTONIAN CIRCUIT (HC) asks, for a given graph G, whether it has a Hamiltonian circuit, that is, a cycle that passes through every vertex in G exactly once. Assume that a graph $c02-math-0119$ , with $c02-math-0120$ , is given by its adjacency matrix (so the input is of length $c02-math-0121$ ). Then, HC is in NP by the following nondeterministic algorithm: we first guess a string $c02-math-0123$ where each y_i is an integer between 1 and n and then verify that (i) y forms a permutation of $c02-math-0127$ and (ii) for each i, $c02-math-0129$ , $c02-math-0130$ , and $c02-math-0131$ . Note that y is of length $c02-math-0133$ and the checking of conditions (i) and (ii) can be done in time $c02-math-0134$ .

Example 2.4

(INTEGER PROGRAMMING). The problem INTEGER PROGRAMMING (IP) asks, for a given pair (A,b), where A is an $c02-math-0137$ integer matrix and b is an n-dimensional integer vector, whether there exists an m-dimensional integer vector x such that $c02-math-0142$ .¹ Like the above examples, in order to demonstrate that $c02-math-0149$ , we may guess an m-dimensional integer vector x and check whether x satisfies $c02-math-0153$ . However, for the purpose of proving $c02-math-0154$ , we need to make sure that if the problem has a solution, then there is a solution of polynomial size. That is, we need to show that if $c02-math-0155$ for some y, then there exists a vector x satisfying $c02-math-0158$ whose elements are integers of length at most $c02-math-0159$ for some polynomial p, where α is the maximum absolute value of elements in A and b and $c02-math-0164$ . (The length of an integer k > 0 written in the binary form is $c02-math-0166$ .) Note that the inputs A and b have the total length $c02-math-0169$ , and hence, the length of the above solution x is polynomially bounded by the input length. We establish this result in the following three lemmas. For any square matrix X, we let $c02-math-0172$ denote its determinant. (In the following three lemmas, $c02-math-0173$ denotes the absolute value of a real number x, not the length of the codes for x.)

Lemma 2.5

Proof

Lemma 2.6

Proof

Lemma 2.7

Proof

Let a_i denote the ith row of A and b_i the ith component of b. Suppose that $c02-math-0216$ has an integer solution. Then we choose a solution x that maximizes the the number of elements in the following set:

where e_j is the jth m-dimensional unit vector, that is, $c02-math-0222$ , with the jth component equal to 1 and the rest equal to 0. We first prove that the rank of B_x is m. For the sake of contradiction, suppose that the rank of B_x is less than m. Then, by Lemma 2.6, we can find an m-dimensional nonzero integer vector z such that for any $c02-math-0230$ , $c02-math-0231$ and each component of z does not exceed $c02-math-0233$ . Note that for each $c02-math-0234$ , $c02-math-0235$ implies that the jth component z_j of z is 0 because $c02-math-0239$ . As z is nonzero, $c02-math-0241$ for some k, $c02-math-0243$ , and for this k, $c02-math-0245$ , and so $c02-math-0246$ . Set $c02-math-0247$ or $c02-math-0248$ such that $c02-math-0249$ . (This is possible because $c02-math-0250$ .) Note that for every $c02-math-0251$ , we have $c02-math-0252$ , and so $c02-math-0253$ , and for every $c02-math-0254$ , $c02-math-0255$ and, hence, $c02-math-0256$ . Thus, B_y contains B_x. Moreover, for $c02-math-0259$ , $c02-math-0260$ . Thus, y is an integer solution of $c02-math-0262$ . By the maximality of B_x, $c02-math-0264$ . So, we have shown that for each solution x that maximizes B_x there is a solution y with $c02-math-0268$ of which the absolute value of the kth component is less than that of x. Applying the same procedure to y, we can decrease the absolute value of the kth component again. However, it cannot be decreased forever, and eventually, a contradiction would occur. The above argument establishes that B_x must have rank m.

Now, choose m linearly independent vectors d₁, $c02-math-0277$ , d_m from B_x. Denote $c02-math-0280$ . Then, by the definition of B_x, $c02-math-0282$ for all $c02-math-0283$ . Applying Cramer's rule to the system of equations $c02-math-0284$ , $c02-math-0285$ , we obtain a representation of x in terms of c_i's: $c02-math-0288$ , where D is a square submatrix of $c02-math-0290$ and D_i is a square matrix obtained from D by replacing the ith column by vector $c02-math-0294$ . Note that the determinant of any submatrix of $c02-math-0295$ is just the determinant of a submatrix of A. By the Laplace expansion and Lemma 2.5, it is easy to see that $c02-math-0297$ $c02-math-0297a$ .

2.2 Cook's Theorem

The notion of reducibilities was first developed in recursion theory. In general, a reducibility $c02-math-0298$ is a binary relation on languages that satisfies the reflexivity and transitivity properties and, hence, it defines a partial ordering on the class of all languages. In this section, we introduce the notion of polynomial-time many-one reducibility. Let $c02-math-0299$ and $c02-math-0300$ be two languages. We say that A is many-one reducible to B, denoted by $c02-math-0303$ , if there exists a computable function $c02-math-0304$ such that for each $c02-math-0305$ , $c02-math-0306$ if and only if $c02-math-0307$ . If the reduction function f is further known to be computable in polynomial time, then we say that A is polynomial-time many-one reducible to B and write $c02-math-0311$ . It is easy to see that polynomial-time many-one reducibility does satisfy the reflexivity and transitivity properties and, hence, indeed is a reducibility.

Proposition 2.8

Note that if $c02-math-0318$ and $c02-math-0319$ , then $c02-math-0320$ . In general, we say a complexity class $c02-math-0321$ is closed under the reducibility $c02-math-0322$ if $c02-math-0323$ and $c02-math-0324$ imply $c02-math-0325$ .

Proposition 2.9

Note that the complexity class $c02-math-0327$ is not closed under $c02-math-0328$ . People sometimes, therefore, study a weaker class of exponential-time computable sets EXPPOLY $c02-math-0329$ , which is closed under $c02-math-0330$ .

For any complexity class $c02-math-0331$ that is closed under a reducibility $c02-math-0332$ , we say a set B is $c02-math-0334$ -hard for class $c02-math-0335$ if $c02-math-0336$ for all $c02-math-0337$ and we say a set B is $c02-math-0339$ -complete for class $c02-math-0340$ if $c02-math-0341$ and B is $c02-math-0343$ -hard for $c02-math-0344$ . For convenience, we say a set B is $c02-math-0346$ -complete if B is $c02-math-0348$ -complete for the class $c02-math-0349$ .² Thus, a set B is NP-complete if $c02-math-0354$ and $c02-math-0355$ for all $c02-math-0356$ . An NP-complete set B is a maximal element in NP under the partial ordering $c02-math-0359$ . Thus, it is not in P if and only if $c02-math-0360$ .

Proposition 2.10

In recursion theory, the halting problem is the first problem proved to be complete for the class of recursively enumerable (r.e.) sets under the reducibility $c02-math-0364$ . As the class of r.e. sets properly contains the class of recursive sets, the halting problem and other complete sets for the class of r.e. sets are not recursive. The analogous problem for the class NP, called the time-bounded halting problem for NTMs, is our first NP-complete problem. (Again, for a natural problem Π that asks whether the given input x satisfies $c02-math-0367$ , we say it is NP-complete to mean that the set $c02-math-0368$ is NP-complete.)

BOUNDED HALTING PROBLEM (BHP): Given the code x of an NTM M_x, an input y and a string 0^t determine whether machine M accepts y within t moves.

Theorem 2.11

Proof

The above theorem demonstrates that NP contains at least one complete problem. By the transitivity property of $c02-math-0397$ , we would like to prove other NP-complete problems by reducing a known NP-complete problem to them, which is presumably easier than reducing all problems in NP to them. However, the problem BHP, being a problem concerning with the properties of NTMs, is hardly a natural problem. To prove the NP-completeness of natural problems, we first need a natural NP-complete problem. Our first natural NP-complete problem is the satisfiability problem SAT. It was first proved to be NP-complete by Stephen Cook in 1970 (Cook, 1971).

Theorem 2.12

Proof

The fact that SAT is in NP has been proved in Example 2.1. We need to prove that for each $c02-math-0398$ , $c02-math-0399$ SAT. Let $c02-math-0400$ , where $c02-math-0401$ is aone-tape NTM with time bound p(n) for some polynomial p. Then, we need to find a Boolean formula F_x for each input string x such that $c02-math-0406$ if and only if F_x is satisfiable. To do so, let an input string x of length n be given. As M halts on x in p(n) moves, the computation of M(x) has at most $c02-math-0414$ configurations. We may assume that there are exactly $c02-math-0415$ configurations by adding dummy moves from a halting configuration, that is, we allow $c02-math-0416$ if α is a halting configuration. Furthermore, we may assume that each configuration is of length p(n), where each symbol a in a configuration is either a symbol in Γ or a symbol in $c02-math-0421$ . (In the latter case, symbol $c02-math-0422$ indicates that the tape head is scanning this square and the current state is q.) Now, for each triple $c02-math-0424$ , with $c02-math-0425$ , $c02-math-0426$ , and $c02-math-0427$ , we define a Boolean variable $c02-math-0428$ to denote the property that the jth square of the ith configuration of the computation of M(x) has the symbol a.

We will construct a Boolean formula F_x of these variables $c02-math-0434$ , such that F_x is satisfiable if and only if the following conditions hold under the above interpretation of the variables $c02-math-0436$ .

For each pair (i,j), with $c02-math-0438$ and $c02-math-0439$ , there is exactly one $c02-math-0440$ such that $c02-math-0441$ . (Based on the above interpretation of variables $c02-math-0442$ , this means that each square of the ith configuration holds exactly one symbol.)
For each pair (j,a), with $c02-math-0445$ and $c02-math-0446$ , $c02-math-0447$ if and only ifthe jth symbol in the initial configuration of M(x) is a.
$c02-math-0451$ for some j, $c02-math-0453$ , and some $c02-math-0454$ . (This means that the p(n)th configuration of M(x) contains a final state.)
For each i such that $c02-math-0458$ , the $c02-math-0459$ th configuration is one of the next configurations of the ith configuration.

Using the above interpretation of the variables $c02-math-0461$ , it is easy to see that the above four conditions are equivalent to the condition that the configurations defined by variables $c02-math-0462$ form an accepting computation of M(x).

The first three conditions are easy to translate into Boolean formulas:

where for each j, $c02-math-0466$ , x_j denotes the jth symbol of x.

For the fourth condition, we first observe a simple relation between consecutive configurations. For each configuration α and each k, $c02-math-0472$ , let α_k denote the kth symbol of α. Assume that the ith configuration of M(x) is α and the $c02-math-0479$ th is β. Then, we can verify this fact locally on the symbols $c02-math-0481$ , α_k, $c02-math-0483$ , $c02-math-0484$ , β_k, and $c02-math-0486$ for each k from 1 to p(n). (To avoid problems around the two ends, we may add blank symbols at positions 0 and $c02-math-0489$ to each configuration.) More precisely, the following conditions are equivalent to $c02-math-0490$ :

If $c02-math-0491$ , then $c02-math-0492$ ; and
If $c02-math-0493$ , then $c02-math-0494$ , where $c02-math-0495$ is the subrelation of $c02-math-0496$ restricted to configurations of length 3.

To translate the above condition (4.2) into a Boolean formula, we define, for each pair $c02-math-0497$ and integers i,j, $c02-math-0499$ , $c02-math-0500$ , a Boolean formula $c02-math-0501$ that encodes the relation $c02-math-0502$ , with $c02-math-0503$ . For instance, if $c02-math-0504$ and $c02-math-0505$ are the only two quintuples in Δ that begin with (q,a), then

Now, we can define ϕ₄ as

Define $c02-math-0511$ . It is clear now that F_x is satisfiable if and only if M accepts x.

It is left to verity that F_x is of length polynomial in $c02-math-0516$ and can be uniformly generated from x. Let $c02-math-0518$ and $c02-math-0519$ . It is easy to see that ϕ₁ is of length $c02-math-0521$ , ϕ₂ is of length $c02-math-0523$ , ϕ₃ is of length $c02-math-0525$ , and ϕ₄ is of length $c02-math-0527$ . Together, formula F_x is of length $c02-math-0529$ . Furthermore, these formulas, except for ϕ₂, do not depend on input x (but only on $c02-math-0532$ ), and ϕ₂ is easily derived from x. Therefore, F_x is polynomial-time computable from x, and the theorem is proven.

To apply SAT to prove other natural NP-complete problems, it would be easier to work with Boolean formulas of simpler forms, such as conjunctive normal form (CNF). Recall that a CNF formula is a product of elementary sums. Each factor of a CNF formula F is a clause of F. A CNF formula F is called a 3-CNF formula if each clause (implicant, respectively) of F contains exactly three literals of three distinct variables. The following variation of SAT is very useful for proving new NP-complete problems:

3-SAT: Given a 3-CNF formula, determine whether it is satisfiable.

Corollary 2.13

Proof

We first observe that, in Theorem 2.12, the Boolean formula F_x can be rewritten as a CNF formula of length $c02-math-0542$ . Indeed, ϕ₁ is a product of clauses, ϕ₂ is a product of literals, and ϕ₃ is a single clause. The only subformulas of F_x that are not in CNF are $c02-math-0547$ , each of which is a product of disjunctive normal form (DNF) formulas. These DNF formulas can be transformed, by the distributive law, into CNF formulas of at most 3^k clauses, where k is the maximum number of nondeterministic moves allowed from any configuration. Thus, ϕ₄ can be transformed into a CNF formula of length $c02-math-0551$ . This shows that the problem SAT restricted to CNF formulas remains NP-complete.

Next, we reduce SAT restricted to CNF formulas to SAT restricted to 3-CNF formulas. Let F be a CNF formula. First, we add three variables, w₁, w₂, and w₃, and seven clauses, $c02-math-0556$ , $c02-math-0557$ , $c02-math-0558$ , $c02-math-0559$ , $c02-math-0560$ , $c02-math-0561$ , and $c02-math-0562$ . Note that there is a unique assignmentτ₀ that can satisfy all these seven clauses: $c02-math-0564$ .

Now, we consider each clause of F. A clause of F is of the form $c02-math-0567$ for some k ≥ 1, where each z_j, $c02-math-0570$ , is a literal. We will replace ϕ by a formula ψ as follows:

Case 1. k = 1. We let $c02-math-0574$ .
Case 2. k = 2. We let $c02-math-0576$ .
Case 3. k = 3. We let $c02-math-0578$ .
Case 4. k = 4. We introduce a new variable $c02-math-0580$ . Then, we define $c02-math-0581$ , where w₁ is the new variable defined above. Note that the last three clauses of ψ means $c02-math-0584$ is equivalent to u. Thus, an assignment τ on z_i, $c02-math-0588$ , satisfies ϕ if and only if the assignment $c02-math-0590$ , defined by $c02-math-0591$ for $c02-math-0592$ and $c02-math-0593$ , satisfies ψ.
Case 5. k > 4. We inductively apply the procedure of Case 4 until we have only clauses of three literals left.

We let G be the product of all new clauses ψ. It is easy to check that F is satisfiable if and only if G is satisfiable. The above transformation from ϕ to ψ can be easily done in time polynomial in k, and so it is a polynomial-time reduction from SAT to 3-SAT.

2.3 More NP-Complete Problems

The importance of the notion of NP-completeness is witnessed by thousands of NP-complete problems from a variety of areas in computer science, discrete mathematics, and operations research. Theoretically, all these problems can be proved to be NP-complete by reducing SAT to them. It is practically much easier to prove new NP-complete problems from some other known NP-complete problems that have similar structures as the new problems. In this section, we study some best-known NP-complete problems that may be useful to obtain new NP-completeness results.

VERTEX COVER (VC): Given a graph $c02-math-0603$ and an integer K ≥ 0, determine whether G has a vertex cover of size at most K, that is, determine whether V has a subset V^′ of size $c02-math-0609$ such that each $c02-math-0610$ has at least one end point in $c02-math-0611$ .

Theorem 2.14

Proof

It is easy to see that VC is in NP. To show that VC is complete for NP, we reduce 3-SAT to it.

Let F be a 3-CNF formula with m clauses $c02-math-0614$ over n variables $c02-math-0616$ . We construct a graph G_F of $c02-math-0618$ vertices as follows. The vertices are named x_i, $c02-math-0620$ for $c02-math-0621$ , and c_j,k for $c02-math-0623$ , $c02-math-0624$ . The vertices are connected by the following edges: for each i, $c02-math-0626$ , there is an edge connecting x_i and $c02-math-0628$ ; for each j, $c02-math-0630$ , there are three edges connecting $c02-math-0631$ into a triangle and, in addition, if $c02-math-0632$ , then there are three edges connecting each c_j,k to the vertex named ℓ_k, $c02-math-0635$ . Figure 2.1 shows the graph G_F for $c02-math-0637$ .

Figure 2.1 The graph G_F.

We claim that F is satisfiable if and only if G_F has a vertex cover of size $c02-math-0641$ . First, suppose that F is satisfiable by a truth assignment τ. Let $c02-math-0644$ . Next for each j, $c02-math-0646$ , let $c02-math-0647$ be the vertex of the least index j_k such that $c02-math-0649$ is adjacent to a vertex in S₁. (By the assumption that τ satisfies F, such an index j_k always exists.) Then, let $c02-math-0654$ and $c02-math-0655$ . It is clear that S is a vertex cover for G_F of size $c02-math-0658$ .

Conversely, suppose that G_F has a vertex cover S of size at most $c02-math-0661$ . As each triangle over $c02-math-0662$ must have at least two vertices in S and each edge $c02-math-0664$ has at least one vertex in S, S is of size exactly $c02-math-0667$ with exactly two vertices from each triangle $c02-math-0668$ and exactly one vertex from each edge $c02-math-0669$ . Define $c02-math-0670$ if $c02-math-0671$ and $c02-math-0672$ if $c02-math-0673$ . Then, each clause C_j must have a true literal which is the one adjacent to the vertex c_j,k that is not in S. Thus, F is satisfied by τ.

The above construction is clearly polynomial-time computable. Hence, we have proved 3-SAT $c02-math-0679$ VC.

CLIQUE: Given a graph $c02-math-0680$ and an integer K ≥ 0, determine whether G has a clique of size K, that is, whether G has a complete subgraph of size K.INDEPENDENT SET (IS): Given a graph $c02-math-0686$ and an integer K ≥ 0, determine whether G has an independent set of size K, that is, whether there is a subset $c02-math-0690$ of size K such that for any two vertices $c02-math-0692$ , $c02-math-0693$ .