SHEN’S CLASS NOTES
Chapter 34
NP-Completeness
34.1 Basic Concepts
After long time study, people found that some problems can be efficiently solved, and some problems are so difficult that only exponential time algorithms are known for them or even no algorithm at all.
In order to study the intrinsic complexity of computational problems, we would like to classify problems into different classes based on their difficulty levels.
If a problem can be solved in time that is a polynomial function of n, where n is the input size, we say that this problem belongs to class P. Class P problems are called tractable because they can be solved in polynomial time. A problem that requires super-polynomial time is called intractable.
There is a class of problems whose tractability is not known yet. We call this class NP-complete (NPC). If a problem belongs to NPC class, then it is a hard problem because no body can provide a polynomial algorithm for it so far. However, it has not been proved yet that they are indeed not polynomial solvable.
In order to study the intrinsic complexity of problems, we introduce the NP class. A problem belongs to the NP class if it can be solved by an NP algorithm in polynomial time. An NP algorithm is an algorithm run on a powerful but hypothetical computing model called non-deterministic machine model. All NPC problems can be solved by an NP algorithm in polynomial time. Moreover, it is proved that if any NPC problem can be solved in the future by a (deterministic) polynomial algorithm, then all NP problems can be solved too. This is the reason why we use the name NP-Complete for such a problem. On the other hand, if any NPC problem is proved to be intractable in the future, then all NPC problems are intractable.
Encodings
The complexity of a problem is closely related to the input size which depends on the encoding of the problem. For example, if we want to encode the number 99. Its decimal representation, binary representation, and unary representation are:
(99)10(uses two digits)
(1100011)2(uses 7 digits)
(1111…1) 1(uses 99 digits).
So, we need to say few words about the encodings.
Two different encodings e1 and e2 are called polynomial related for a problem I if there is a polynomial computable functions f and g such that f(e1(i))=e2(i) and g(e2(i)) = e1(i) for any problem instance i. Obviously, if encodings e1 and e2 are polynomial related for problem I, then the problem I can be solved in polynomial time under encoding e1 if and only if I can be solved in polynomial time under encoding e2.
We notice that almost all encoding methods are polynomial related except “expensive” encoding such as unary encoding. Suppose we use binary encoding for a number N, we need log2N bits. Now, if we use base b system to represent N, then we need logbN digits. However,
log2N = (log2b)(logbN) = klogbN,
where k = log2bis a constant.
Therefore, using base two encoding or base b encoding will affect the input size only by a constant factor.
In general, if an encoding e uses an alphabet of b symbols, we can always use two symbols {0, 1} to encode each symbol with log2b bits. Thus, any encoding can be translated into a binary encoding without affect the complexity.
We can assume that any “reasonable” encoding,particularly, binary encoding, can be used in our discussion of NP-Completeness theory,
Decision Problems vs. Optimization Problems
Many problems are optimization problems for which we wish to find the best solutions. For example, find a shortest path in between two vertices of a graph, find the largest compatible set of activities, find the MST for a graph.
The NP-completeness theory does not directly apply to the optimization problems. It is based on “decision problems.”
Definition 1Any problem for which the answer is either yes or no is called a decision problem.
Although the discussion on NP-Completeness is restricted for decision problems, it usually can be indirectly applied to optimization problems. For example, finding a path from vertex u to vwith minimum number of edges is an optimization problem. We can cast this problem as a decision problem as follows:
Given a graph G(V, E) and two vertices u, vV, does there exists a path from u to v with distance k or less? We denote the coding of this problem by <G, u, v, k>.
If this decision problem can be solved by an algorithm A(G, u, v, k), then the optimization problem can be solved in the following way:
Shortest-path(G, u, v)
1k 1
2while A(G, u, v, k) = ‘no’
3 do {kk + 1
4 A(G, u, v, k)
5 }
6returnk
7End
Obviously, the above algorithm is polynomial if A(G, u, v, k) is a polynomial algorithm. This algorithm finds the length k of the shortest path, it does not actually produce the path. However, it is not hard to design a simple algorithm that can actually produce the path. We leave this to students.
From now on, we only discuss decision problems unless specified otherwise.
Polynomial reductions
Definition 2Let A and B be two problems, we say that A polynomial reduces to B, denoted by A B, if there is a procedure called reduction algorithm that transforms any instance of A into an instance of B with the following characteristics:
(1)The transformation takes polynomial time.
(2)The answer for is yes if and only if the answer for is yes.
Obviously, if A B and B is polynomial time solvable, then A is also polynomial solvable.
A Formal-Language Framework
Since the formal-language is a powerful tool in establishing NPC theory, here we review some basic notions about formal languages.
Definition 3An alphabet is a finite set of symbols.
Examples are: = {0, 1}, = {a, b, c}, = {a, b, …, z}.
Definition 4A language L over is any set of strings made up of symbols from.
Suppose = {0, 1}, L = {10, 11, 101, 111, 1011, …, } is the language which contains the binary representations of all prime numbers.
Special symbols and are used to represent the empty string and the empty language respectively. Moreover, * is used to represent the set of all binary strings. That is,
* = {, 0, 1, 00, 01, 10, 11, 000, 001, …}.
Every language L is a subset of *. * itself is a language also.
Definition 5Let L1 and L2 be two languages, their concatenation is a language defined by
L1 L2= {x1x2| x1 L1, x2 L2}.
For example,
L1= {10, 1100, 111000, …} = {1n0n | n 1},
L2= {01, 0011, 000111, …} = {0n1n | n 1},
L1 L2= {1001, 100011, …} = {1n0n+m1m | m, n 1}.
Definition 6Let L be a language, its complement and Kleene star are languages defined by:
=* - L, and
L* = {} L L2 L3…
Let Q be a decision problem, x be an instance of the problem, Q(x) be the answer to the instance x. Moreover, we use Q(x) = 1 and Q(x) = 0 to represent that the answer is yes or no respectively. Then, the problem Q can be characterized by the following language:
L = { x* | Q(x) = 1}.
Definition 7An algorithm A is said to accept a string x {0, 1}* if given input x, the algorithm’s output A(x) = 1. The algorithm A is said to reject a string x if A(x) = 0.
Definition 8 Given an algorithm A, we define the language accepted by A to be the set of strings accepted by A:
L = {x | x {0, 1}* and A(x) = 1}.
Definition 9A language L is decided by an algorithm A if every string in L is accepted by A and every string not in L is rejected by A.
Now, we are ready to define class P.
Class P
The class P is the set of decision problems that can be solved (decided) in polynomial time.
P = {L | L {0, 1}* and there exists an algorithm A that decides L in polynomial time}.
The following theorem shows that accepting a language in polynomial time means deciding a language in polynomial time. So, we only need to show there is a polynomial time algorithm to accept a language to prove that it is in class P.
Theorem 34.2
P = {L | L is accepted by a polynomial time algorithm}.
Proof. We need only show that if L is accepted by a polynomial time algorithm A, then we can find an algorithm A’ that decides L in polynomial time.
Assume algorithm A accepts L in time O(nk) for a fixed k. This means that, for any string x of size n in L, algorithm A can produce A(x) = 1 within T =cnk steps, where c is a constant number. Now, we can design an algorithm A’ in this way:
Let A’ to simulate the actions of A on an input x until A stops or reaches T steps. Then, A’ checks the result of A. If A accepts x, A’ accepts x by output 1. If algorithm A has not accepted x, then A’ rejects x by output 0. Obviously, A’ correctly decides L in polynomial time.
34.2 Polynomial Time Verification
If we are given a decision problem and additional information which proves that the answer to the decision problem is yes, can you design a polynomial algorithm to verify that this information indeed proves the answer is yes?
If you can, then this algorithm is called a polynomial (time) verification algorithm.
For example,if you are given problem <G, u, v, k and you are also given a path from u to v with distance k or less, then, we can easily design a polynomial algorithm that verifies if the path is indeed a path in the graph from u to v, and check if its length is k or less.
The additional information is called a certificate. Obviously, the length of the certificate must be a polynomial function of input size also.
We assume that if the instance of the problem has “no” answer, then no certificate can exist. In this case, the verification algorithm can either give “no” answer or give no answer. In other words, the verification is only responsible for the cases where the instance of the problem has “yes” answer and a correct polynomial-long certificate is always provided.
Usually, when we could not solve a hard problem in polynomial time, we try to design a polynomial verification algorithm for it. We call a polynomial verification algorithm an NP-algorithm.
In the following, we look at another example.
Hamiltonian Cycles
A Hamiltonian cycle of a graph G(V, E) is a simple cycle that goes through every vertex in V exactly once. Agraph that has a Hamiltonian cycle is called Hamiltonian graph. The Hamiltonian cycle problem is a decision problem that asks whether a given graph G has a Hamiltonian cycle or not. In terms of formal language, this problem corresponds to the following language.
HAM-CYCLE = {<G> | G is a Hamiltonian graph}.
This is a difficult problem. So, we consider the verification algorithm.
Suppose we are given a graph G, and also a sequencep of vertices, design a polynomial algorithm that verifies if p represents a Hamiltonian cycle of G.
Obviously, this verification problem can be easily solved in O(n2):
HAM-CYCLE(G(V, E), p)
1Check if every vertex in p belongs to set V.
2Check if the starting and ending vertices are identical.
3Check every other vertex in p to see if they occur exactly once.
4Check if every vertex in G occurs in p.
5Check if every two adjacent vertices u, v in p are also adjacent in G.
6If all above steps passed, return yes, otherwise no.
7End
Definition 10A verification algorithm A(x, y) is a two-argument algorithm that takes an instance x of problem Q and a certificate y of x. This algorithm will produce A(x, y) = 1 if y proves Q(x) = 1.
Note. The verification algorithm only needs be responsible for those certificates y that proves Q(x) = 1. If Q(x) = 0, the algorithm is allowed to produce nothing or runs forever.
The class NP
A language L belongs to class NP if and only if there exists a two-input polynomial-time algorithm A and a constant c such that
L = {x {0, 1}* | there exists a certificate y with |y| = O(|x|c) such that A(x, y) = 1}.
We say that algorithm A verifies language L in polynomial time.
Obviously, HAM-CYCLE NP.
Note that P NP because if L P, then L can be accepted by an algorithm A in polynomial time. So, a certificate exists for any x L and A can be used as a verification algorithm. For example, <G, u, v, k> is in P. If the answer to a graph G is yes, then a path (u, v) with distance k or less exists. So, such a path can serve as a certificate.
Also, note that a certificate is not unique. Any string that can be used to prove that the answer is yes can be used as a certificate. Therefore, x itself can be used as a certificate.
Example 1
The set partition problem takes as input a set S of numbers. The question is whether the numbers can be partitioned into two sets, A and Ā = S – A such that
=
Show that the set-partition problem is in NP.
Solution:
Let the certificate y be a subset Y of the set S. The verification algorithm A takes the following steps to verify:
(1)check if every number in Y is a number in S
(2)compute the sum of all numbers in the set Y
(3)computer the set S – Y
(4)compute the sum of all numbers in the set S- Y
(5)compare the two numbers obtained in (2) and (4) to see it these two numbers are identical. If yes, then return yes.
34.3 NP-Completeness and Reducibility
Definition 11A language L1is polynomial-time reducible to a language L2, written L1pL2, if there exists a polynomial–time computable functionf : {0, 1}* {0, 1}* such that for all x {0, 1}*, x L1 if and only if f(x) L2. The function f is called the reduction function. A polynomial-time algorithm F that computes f is called a reduction algorithm.
Figure 34-1 illustrates the reduction function f.
Fig. 34-1
Note that the reduction function is not one-to-one nor onto function. It may be a many to one function and some instances in L2 may be left unmapped.
Lemma 34.3
If L1, L2 {0, 1}* are languages such that L1pL2, then L2 P implies L1 P.
Proof. Let A2 be a polynomial-time algorithm that decides L2, and let F be a polynomial-time reduction algorithm that computes the reduction function f. We shall show how to design a polynomial-time algorithm A1 that decidesL1.
Fig. 34-2 illustrates the design of A1.
Fig. 34-2
Algorithm A1(x)
1call algorithm F to transform x into f(x)
2call algorithm A2(f(x)) to test if f(x) L2
3if A2(f(x)) = 1//This means f(x) L2
4 thenreturn A1(x) = 1//x L1
5 else return A1(x) = 0 //x L1
6End
Obviously, the algorithm correctly decides L1 and its running time is polynomial because each step in the algorithm needs a polynomial time.
The class NPC
Definition 12A language L {0, 1}* is called NP-Complete if the following two conditions hold:
(1)L NP, and
(2)L’pL for every L’ NP.
If a language L satisfies condition (2), but not necessarily (1), then we say that L is NP-hard.
From the definition, any NP-Complete problem is also a NP-hard problem.
Definition 13The set of all NP-Complete problems is called the NP-Complete class or the NPC class. That is NPC = {L | L is NP-Complete}.
Theorem 4.4
If any NP-Complete problem is polynomial-time solvable, then P = NP. Equivalently, if any problem in NP is not polynomial-time solvable, then no NP-Complete problem is polynomial-time solvable.
Proof.Suppose L P and also L NPC. By the definition of NP-Completeness, L’pL for every L’ NP. From Lemma 34.3, we also have L’ P. Therefore, P = NP. The second statement is the contraposition of the first and it is true also.
So far it is not known if P = NP or P NP although most people believe P NP. This is the most famous open conjecture in computer science. If P = NP, then P = NP = NPC. Otherwise, P NP, NPC NP, and P NPC = as illustrated by Fig. 34-3.
Fig. 34-3
Circuit Satisfiability
We will show that the NPC class is not empty. We will show that the circuit satisfiability problem is NP-Complete.
Definition 14A Boolean combinational circuit composed of AND, OR, and NOT gates is satisfiable if a set of input values can be found such that the output of the circuit is 1.
Example 2
Fig. 34-4 shows two circuits, one is satisfiable and the other is not.
Fig. 34-4
Suppose a combinational circuit is encoded in a binary sequence <c>. Then the circuit satisfiability problem corresponds to the following language:
CIRCUIT-SAT = {<C> | C is a satisfiable circuit}.
Lemma 34.5
CIRCUIT-SAT NP.
Proof. We design a two-input polynomial-time algorithm A that can verify CIRCUIT-SAT. One input is the circuit C and the other is a certificate corresponding to an assignment of Boolean values to the wires of C.
The algorithm A is constructed as follows. For each logic gate, it checks that the value provided by the certificate is correctly computed. Then, if the final output of the entire circuit is 1, the algorithm outputs 1. Otherwise A outputs 0. When the circuit is satisfiable, a certificate exists and has a length that is in the order of the circuit. The time to verify is linear in the number of gates and wires. Thus A is a polynomial-time algorithm. Therefore, CIRCUIT-SAT NP.
Lemma 34.6
CIRCUIT-SAT is NP-hard
Proof.Omitted.
Theorem 34.7
CIRCUIT-SAT NPC.
Proof. This is obtained directly from Lemmas 34.5 and 34.6.
34.4 NP-Completeness Proofs
Lemma 34.8
If L is a language such that L’pL for some L’ NPC, then L is NP-hard. Moreover, if L NP, then L NPC.
Proof.Since L’ is NP-Complete, for any L’’ NP, we have L’’pL’. Because L’pL, we have L’’pL by transitivity. (See Exercise 34.3-2.) Therefore, L is NP-hard. Moreover, if L NP, then L NPC by definition.
A Method for Proving that a language L is NP-Complete
From Lemma 34.8, we often use the following steps to prove that a language L is NP-Complete.
(1)Prove L NP
(2)Select a known NP-Complete language L’
(3)Describe an algorithm Fthat transforms every instance x{0, 1}* of L’ to an instance f(x) of L.
(4)Prove that x L’ if and only if f(x) L for all x{0, 1}*.
(5)Prove that the algorithm F runs in polynomial time.
In the following, we study a NPC problem.
Formula Satisfiability
We define the formula satisfiability problem in terms of the language SAT.
An instance of SAT is a Boolean formula which consists of:
(1)n Boolean variables : x1, x2, …, xn;
(2)m Boolean connectives. Each connective has one or two inputs and one output. Possible connectives are:
, , , ,
(3)Parentheses used to define order of connectives. We assume no redundant parentheses.
A truth assignment for a formula is a set of values for the variables of .
A satisfying assignment is a truth assignment such that = 1.
A formula is satisfiable formula if it has a satisfying assignment.
SAT = {<> | is a satisfiable Boolean formula}.
Example 3
= ((x1x2) ((x1 x3) x4)) x2 is satisfiable.
A satisfying assignment is <x1 = 0, x2 = 0, x3 = 1,x4 = 1>.
= ((0 0) ((0 1) 1)) 0
= (1(1 1)) 1
= (1 0) 1
= 1.
Theorem 34.9
SAT NPC.
Proof.We first prove that SAT NP. Given a certificate consisting of a satisfying assignment for a formula , the verifying algorithm simply replaces each variable in the formula with its corresponding value and then evaluates the expression. This can be done in polynomial time. So, SAT NP.
Now, we prove that SAT NP-hard. We will show that CIRCUIT-SAT p SAT. We will show how to transform a circuit into a formula.
The transformation takes the following steps:
(1)Create n variables x1, x2, …, xn for the n input lines of the circuit.
(2)Let m be the number of gates in the circuit. Create a new variable xn+ifor the output wire of gatei.
(3)For gatei, create a simple formula fi that establishes “if and only if” relation between its input variables and its output variables, 1 i m. Specifically,
(3.1)if gate i is a NOT gate and the input variable is xjthen fi = (xn+ixj);
(3.2)if gate i is a OR gate and the input variables are xr, xr+1, …, xj then fi = (xn+i (xr xr+1…xj));
(3.3)if gate i is a AND gate and the input variables are xr, xr+1, …, xj then fi = (xn+i (xrxr+1…xj)).
(4)Let the xn+m be the variable corresponding to the output wire of the circuit. Then, the formula is
= xn+mf1f2 …fm.
Fig. 34-5 shows an example.
f1 = (x4x3), f2 = (x5 (x1 x2)), f3 = (x6x4),
f4 = (x7 (x1 x2 x4)), f5 = (x8 (x5 x6)),
f6 = (x9 (x6 x7)), f7 = (x10 (x7 x8 x9)).
= x10 (x4x3)
(x5 (x1 x2))
(x6x4)
(x7 (x1 x2 x4))
(x8 (x5 x6))
(x9 (x6 x7))
(x10 (x7 x8 x9)).
Fig. 34-5.
Now we prove that the circuit is satisfiable if and only if is satisfiable.
(1)Suppose the circuit is satisfiable.
Letx1, x2, …, xnsatisfy the circuit. Then, we can use the same set of values for the variables x1, x2, …, xnin the formula . Moreover, we use the value output from gate i for variable xn+iin . Because each formula ficorrectly defines the function of gate i, the value of each fiwill be 1. So, if we evaluate , we will get 1 which means, is satisfiable.
(2)Suppose is satisfiable.
Let a set of values of x1, x2, …, xn, xn+1, …, xn+m satisfy . Then, we can use the same values of x1, x2, …, xnas the input values to the circuit. Because = 1, each formula fimust equal to one also, as well as xn+m= 1. Because fi correctly defines the function of gate i, the value of output wire from gate i must equal to the value of fn+i. Particularly, the value of the output of the circuit is equal to xn+mwhich is equal to one. Therefore, the circuit is satisfiable.