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 NPhardness 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 NPhardness of the 3satisfiability problem. However, in general the proof of the NPhardness of a given problem need not be generic in nature, but can be accomplished by polynomial time reduction from another NPhard 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_{1}(n) time, and K_{b} is reducible to a problem K_{c} in T_{2}(n) time, then K_{a} is reducible to K_{c} in T_{2}(T_{1}(n)) time. Moreover, T_{2}(T_{1}(n)) is polynomial if T_{1}(n) and T_{2}(n) are so.
The proofs of the following two theorems exhibit the NPhardness 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 NPcomplete problem.
Proof Consider a Turing machine M that on any given instance (a_{1}, . . . , a_{N }, b) of the problem nondeterministically assigns values from {0, 1} to v_{1}, . . . , v_{N }, checks whether a_{1}v_{1} + + 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 NPhard consider any instance E of the 3satisfiability problem. Let x_{1}, . . . , x_{m} denote the variables in the Boolean expression E. E is a conjunction c_{1} c_{k} of some clauses c_{1}, . . . , 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.
x_{1} + _{1}  =  1  
x_{m} + _{m}  =  1  
c_{1 1} + c_{1 2} + c_{1 3} + y_{1 1} + y_{1 2}  =  3  
c_{k 1} + c_{k 2} + c_{k 3} +y_{k 1} +y_{k 2}  =  3 
The system S has the variables x_{1}, . . . , x_{m}, _{1}, . . . , _{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_{1}, . . . , z_{2m+2k} in the vector form stand for the variables x_{1}, . . . , x_{m}, _{ 1}, . . . , _{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 righthand 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_{1} 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_{1} + + a_{2m+2k} depends only on the ith digits of a_{1}, . . . , 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 3satisfiability problem is satisfiable if and only if the instance (a_{1}, . . . , a_{2m+2k}, b) of the 0  1 knapsack problem has a positive solution. Moreover, a polynomially timebounded, deterministic Turing transducer can similarly construct corresponding instance of the 0  1 knapsack problem, from each instance E of the 3satisfiability problem. Consequently, the NPhardness of the 0  1 knapsack problem follows from the NPhardness of the 3satisfiability problem.
Example 5.4.1 Consider the Boolean expression E of the form (x_{1}x_{2}¬x_{3})(¬x_{2}x_{3}¬x_{4})(x_{1}x_{3}x_{4})(¬x_{1}x_{2}x_{4}). E is an instance of the 3satisfiability 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 previous examples of NPcomplete 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 NPcomplete problem.
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 NPhardnes of the clique problem consider any instance E of the 3satisfiability problem. As in the proof of the previous result, let x_{1}, . . . , x_{m} denote the variables in the Boolean expression E. E is a conjunction c_{1} c_{k} of some clauses c_{1}, . . . , 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_{1}, d_{2}, d_{3})) of an assignment (d_{1}, d_{2}, d_{3}) that satisfies a clause C_{i}. The node that corresponds to a pair (c_{i}, (d_{1}, d_{2}, d_{3})) is labeled by the set {x_{i 1} = d_{1}, x_{i 2} = d_{2}, x_{i 3} = d_{3}}, 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_{1}, x_{i 2} = d_{2}, x_{i 3} = d_{3}} and a node labeled by a set {x_{j 1} = d'_{1}, x_{j 2} = d'_{2}, x_{j 3} = d'_{3}} 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 timebounded, deterministic Turing transducer can in a similar way determine a corresponding instance (G, k) of the clique problem for each instance E of the 3satisfiability problem. Therefore, implying the NPhardness of the clique problem.
Example 5.4.2 Let E be the Boolean expression (x_{1}x_{2}¬x_{3})(¬x_{2}x_{3}¬x_{4})(x_{1}x_{3}x_{4})(¬x_{1}x_{2}x_{4}). Let G be the graph in Figure 5.4.1.

From the definition of NPcompleteness, it follows that P is equal to NP if and only if there is an NPcomplete problem in P.
It should be noticed that all the known algorithms, for the NPcomplete 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_{1}, . . . , 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 NPcomplete problems.