5.4  More NP-Complete Problems

      The 0 - 1 Knapsack Problem
      From Boolean Expression to a System of Linear Equations
      From a System of Linear Equations to an Instance of the 0 - 1 Knapsack Problem
      The Clique Problem

The NP-hardness of the satisfiability problem was demonstrated by exhibiting the existence of a polynomial time reduction, from each problem in NP to the satisfiability problem. A similar approach was used for showing the NP-hardness of the 3-satisfiability problem. However, in general the proof of the NP-hardness of a given problem need not be generic in nature, but can be accomplished by polynomial time reduction from another NP-hard problem.

A proof by reduction is possible because the composition of polynomial time reductions is also a polynomial time reduction. That is, if a problem K_a is reducible to a problem K_b in T₁(n) time, and K_b is reducible to a problem K_c in T₂(n) time, then K_a is reducible to K_c in T₂(T₁(n)) time. Moreover, T₂(T₁(n)) is polynomial if T₁(n) and T₂(n) are so.

 The 0 - 1 Knapsack Problem

The proofs of the following two theorems exhibit the NP-hardness of the problems in question by means of reduction.

Theorem 5.4.1    The problem defined by the following pair, called the 0 - 1 knapsack problem, is an NP-complete problem.

Domain:

{ (a₁, . . . , a_N , b) | N 1, and a₁, . . . , a_N , b are natural numbers }.

Question:

Are there v₁, . . . , v_N in {0, 1} such that a₁v₁ + + a_N v_N = b for the given instance (a₁, . . . , a_N , b)?

Proof     Consider a Turing machine M that on any given instance (a₁, . . . , a_N , b) of the problem nondeterministically assigns values from {0, 1} to v₁, . . . , v_N , checks whether a₁v₁ + + a_N v_N = b, and accepts the input if and only if the equality holds. M can be of polynomial time complexity. Therefore the 0 - 1 knapsack problem is in NP.

To show that the 0 - 1 knapsack problem is NP-hard consider any instance E of the 3-satisfiability problem. Let x₁, . . . , x_m denote the variables in the Boolean expression E. E is a conjunction c₁ c_k of some clauses c₁, . . . , c_k. Each C_i is a disjunction c_{i 1} c_{i 2} c_{i 3} of some literals c_{i 1}, c_{i 2}, c_{i 3}. Each c_{i j} is a variable x_t, or a negation ¬x_t of a variable x_t, for some 1 t m.

 From Boolean Expression to a System of Linear Equations

From the Boolean expression E a system S of linear equations of the following form can be constructed.

x1 + 1	=	1
xm + m	=	1
c1 1 + c1 2 + c1 3 + y1 1 + y1 2	=	3
ck 1 + ck 2 + ck 3 +yk 1 +yk 2	=	3

The system S has the variables x₁, . . . , x_m, ₁, . . . , _m, y_{1 1}, . . . , y_{k 2}. The variable x_t in S corresponds to the literal x_t in E. The variable _t in S corresponds to the literal ¬x_t in E. c_{i j} stands for the variable x_t in S, if x_t is the jth literal in C_i. c_{i j} stands for the variable _t in S, if ¬x_t is the jth literal in C_i.

Each equation of the form x_i + _i = 1 has a solution over {0, 1} if and only if either x_i = 1 and _i = 0, or x_i = 0 and _i = 1. Each equation of the form c_{i 1} + c_{i 2} + c_{i 3} + y_{i 1} + y_{i 2} = 3 has a solution over {0, 1} if and only if at least one of the equalities c_{i 1} = 1, c_{i 2} = 1, and c_{i 3} = 1 holds. It follows that the system S has a solution over {0, 1} if and only if the Boolean expression E is satisfiable.

 From a System of Linear Equations to an Instance of the 0 - 1 Knapsack Problem

The system S can be represented in a vector form as follows.

The variables z₁, . . . , z_2m+2k in the vector form stand for the variables x₁, . . . , x_m, ₁, . . . , _m, y_{1 1}, . . . , y_{k 2} of S, respectively. a_{i j} is assumed to be the coefficient of z_j in the ith equation of S. b_i is assumed to be the constant in the right-hand side of the ith equation in S.

Similarly, the system S can also be represented by the equation H of the following form.

In H, each a_j stands for the integer whose decimal representation is a_{1 j} a_{m+k j}. Similarly, b stands for the integer whose decimal representation is b₁ b_m+k. The representation is possible because the sum a_{i 1} + + a_{i 2m+2k} is either equal to 2 or to 5 for each 1 i m + k. That is, the ith digit in the sum c = a₁ + + a_2m+2k depends only on the ith digits of a₁, . . . , a_2m+2k. It follows that S is satisfiable over {0, 1} if and only if H is satisfiable over {0, 1}.

As a result, the instance E of the 3-satisfiability problem is satisfiable if and only if the instance (a₁, . . . , a_2m+2k, b) of the 0 - 1 knapsack problem has a positive solution. Moreover, a polynomially time-bounded, deterministic Turing transducer can similarly construct corresponding instance of the 0 - 1 knapsack problem, from each instance E of the 3-satisfiability problem. Consequently, the NP-hardness of the 0 - 1 knapsack problem follows from the NP-hardness of the 3-satisfiability problem.

Example 5.4.1    Consider the Boolean expression E of the form (x₁x₂¬x₃)(¬x₂x₃¬x₄)(x₁x₃x₄)(¬x₁x₂x₄). E is an instance of the 3-satisfiability problem. The Boolean expression is satisfiable if and only if the following system S of linear equations has a solution over {0, 1}.

On the other hand, the system S has a solution over {0, 1} if and only if the equation H of the following form has a solution over {0, 1}. The leading zeros are ignored in the constants of H.

The expression E is satisfiable if and only if the instance (10001010, 1001001, 100110, 10011, 10000001, 1000100, 101000, 10100, 1000, 1000, 100, 100, 10, 10, 1, 1, 11113333) of the 0 - 1 knapsack problem has a positive solution.

 The Clique Problem

The previous examples of NP-complete problems deal with Boolean expressions and linear equations. The following example deals with graphs.

Theorem 5.4.2    The problem defined by the following pair, called the clique problem, is an NP-complete problem.

Domain:

{ (G, k) | G is a graph and k is a natural number }.

Question:

Does G has a clique of size k for the given instance (G, k)? (A clique is a subgraph with an edge between each pair of nodes. The number of nodes in a clique is called the size of the clique.)

Proof     Consider a Turing machine M that on a given instance (G, k) of the clique problem proceeds as follows. M starts by nondeterministically choosing k nodes in G. Then it determines whether there is an edge in G between each pair of the k chosen nodes. If so, then M accepts the input; otherwise it rejects the input. M is of polynomial time complexity. Consequently the clique problem is in NP.

To show the NP-hardnes of the clique problem consider any instance E of the 3-satisfiability problem. As in the proof of the previous result, let x₁, . . . , x_m denote the variables in the Boolean expression E. E is a conjunction c₁ c_k of some clauses c₁, . . . , c_k. Each C_i is a disjunction c_{i 1} c_{i 2} c_{i 3} of some literals c_{i 1}, c_{i 2}, c_{i 3}. Each c_{i j} is a variable x_t, or a negation ¬x_t of a variable x_t, for some 1 t m. From the Boolean expression E a graph G of the following form can be constructed.

The graph G has a node corresponding to each pair (c_i, (d₁, d₂, d₃)) of an assignment (d₁, d₂, d₃) that satisfies a clause C_i. The node that corresponds to a pair (c_i, (d₁, d₂, d₃)) is labeled by the set {x_{i 1} = d₁, x_{i 2} = d₂, x_{i 3} = d₃}, where x_{i 1}, x_{i 2}, x_{i 3} are assumed to be the variables used in c_{i 1}, c_{i 2}, c_{i 3}, respectively. It follows that for each C_i, the graph G has seven associated nodes.

The graph G has an edge between a node labeled by a set {x_{i 1} = d₁, x_{i 2} = d₂, x_{i 3} = d₃} and a node labeled by a set {x_{j 1} = d'₁, x_{j 2} = d'₂, x_{j 3} = d'₃} if and only if no variable x_t has conflicting assignments in the two sets, 1 t m.

By construction, no pair of nodes associated with the same clause C_i have an edge between them. On the other hand, the edges between the nodes that correspond to each pair of clauses, relate exactly those assignments to the variables that satisfy both clauses simultaneously. Consequently, the Boolean expression E is satisfiable if and only if G has a clique of size k.

A polynomially time-bounded, deterministic Turing transducer can in a similar way determine a corresponding instance (G, k) of the clique problem for each instance E of the 3-satisfiability problem. Therefore, implying the NP-hardness of the clique problem.

Example 5.4.2    Let E be the Boolean expression (x₁x₂¬x₃)(¬x₂x₃¬x₄)(x₁x₃x₄)(¬x₁x₂x₄). Let G be the graph in Figure 5.4.1.

Figure 5.4.1 A graph G which relates the assignments that satisfy the clauses of the Boolean expression (x1 x2 ¬x3) (¬x2 x3 ¬x4) (x1 x3 x4) (¬x1 x2 x4).

From the definition of NP-completeness, it follows that P is equal to NP if and only if there is an NP-complete problem in P.

It should be noticed that all the known algorithms, for the NP-complete problems, are in essence based on exhaustive search over some domain. For instance, in the case of the satisfiability problem, an exhaustive search is made for an assignment to the variables that satisfies the given expression. In the case of the 0 - 1 knapsack problem, the exhaustive search is made for a subset of a given multiset {a₁, . . . , a_N }, whose values sum up to some given value b. In the case of the clique problem, the exhaustive search is made for a clique of the desired size. In all of these cases the search is over a domain of exponential size, and so far it seems this is the best possible for the NP-complete problems.

[next] [prev] [prev-tail] [front] [up]