7 TIME COMPLEXITY Even when a problem is decidable and thus computationally solvable in principle, it may not be solvable in practice if the solution requires an inordinate amount of time or memory. In this final part of the book we introduce computational complexity theory—an investigation of the time, memory, or other resources required for solving computational problems. We begin with time. Our objective in this chapter is to present the basics of time complexity theory. First we introduce a way of measuring the time used to solve a problem. Then we show how to classify problems according to the amount of time required. After that we discuss the possibility that certain decidable problems require enormous amounts of time and how to determine when you are faced with such a problem. 7.1 MEASURING COMPLEXITY Let's begin with an example. Take the language A = {0felfc| k > 0}. Obviously A is a decidable language. How much time does a single-tape Turing machine need to decide A? We examine the following single-tape TM Mi for A. We give 247 248 CHAPTER 7 / TIME COMPLEXITY the Turing machine description at a low level, including the actual head motion on the tape so that we can count the number of steps that Mi uses when it runs. Mi = "On input string w. 1. Scan across the tape and reject if a 0 is found to the right of a 1. 2. Repeat if both Os and Is remain on the tape: 3. Scan across the tape, crossing off a single 0 and a single 1. 4. If Os still remain after all the Is have been crossed off, or if Is still remain after all the Os have been crossed off, reject. Otherwise, if neither Os nor Is remain on the tape, accept." We analyze the algorithm for TM Mi deciding A to determine how much time it uses. The number of steps that an algorithm uses on a particular input may depend on several parameters. For instance, if the input is a graph, the number of steps may depend on the number of nodes, the number of edges, and the maximum degree of the graph, or some combination of these and/or other factors. For simplicity we compute the running time of an algorithm purely as a function of the length of the string representing the input and don't consider any other parameters. In worst-case analysis, the form we consider here, we consider the longest running time of all inputs of a particular length. In average-case analysis, we consider the average of all the running times of inputs of a particular length. definition 7.1 Let M be a deterministic Turing machine that halts on all inputs. The running time or time complexity of M is the function /: Af—>J\f, where f(n) is the maximum number of steps that M uses on any input of length n. If /(n) is the running time of M, we say that M runs in time f(n) and that M is an f(n) time Turing machine. Customarily we use n to represent the length of the input. BIG-O AND SMALL-O NOTATION Because the exact running time of an algorithm often is a complex expression, we usually just estimate it. In one convenient form of estimation, called asymptotic analysis, we seek to understand the running time of the algorithm when it is run on large inputs. We do so by considering only the highest order term of the expression for the running time of the algorithm, disregarding both the coefficient of that term and any lower order terms, because the highest order term dominates the other terms on large inputs. 7.1 MEASURING COMPLEXITY 249 For example, the function f(n) = 6n3 + 2n2 + 20n + 45 has four terms, and the highest order term is 6n3. Disregarding the coefficient 6, we say that / is asymptotically at most n3. The asymptotic notation or big-0 notation for describing this relationship is f(n) = 0(n3). We formalize this notion in the following definition. Let 7Z+ be the set of nonnegative real numbers. definition 7.2 Let / and g be functions /, g: M—>7Z+. Say that f(n) — 0(g(n)) if positive integers c and no exist such that for every integer n > no f{n) < cg(n). When f(n) = 0(g(n)) we say that g(n) is an upper bound for f(n), or more precisely, that g(n) is an asymptotic upper bound for f(n), to emphasize that we are suppressing constant factors. Intuitively, f(n) = 0(g{n)) means that / is less than or equal to g if we disregard differences up to a constant factor. You may think of O as representing a suppressed constant. In practice, most functions / that you are likely to encounter have an obvious highest order term h. In that case write f(n) = 0(g(n)), where g is h without its coefficient. example 7.3 Let /i (n) be the function 5n3 + 2n2 + 22n + 6. Then, selecting the highest order term 5n3 and disregarding its coefficient 5 gives fi(n) — 0(n3). Let's verify that this result satisfies the formal definition. We do so by letting c be 6 and n0 be 10. Then, 5n3 + 2n2 + 22n + 6 < 6n3 for every n > 10. In addition, fi(n) — 0(n4) because n4 is larger than n3 and so is still an asymptotic upper bound on fi. However, fi(n) is not 0(n2). Regardless of the values we assign to c and no, the definition remains unsatisfied in this case. example 7.4 .............................................................................................................................. The big-0 interacts with logarithms in a particular way. Usually when we use logarithms we must specify the base, as in x = log2 n. The base 2 here indicates that this equality is equivalent to the equality 2X = n. Changing the value of the base b changes the value of log6 n by a constant factor, owing to the identity log^n = log2 nj log2 b. Thus, when we write f(n) = O(logn), specifying the base is no longer necessary because we are suppressing constant factors anyway. Let f2(n) be the function 3n log2 n + 5n log2 log2 n + 2. In this case we have f2(n) — 0(n log n) because log n dominates log log n. 250 CHAPTER 7 / TIME COMPLEXITY Big-0 notation also appears in arithmetic expressions such as the expression f(n) = 0(n2) + 0(n). In that case each occurrence of the O symbol represents a different suppressed constant. Because the 0(n2) term dominates the 0(n) term, that expression is equivalent to f(n) = 0(n2). When the O symbol occurs in an exponent, as in the expression f(n) = 2°(n\ the same idea applies. This expression represents an upper bound of 2cn for some constant c. The expression f(n) — 2°^logn^ occurs in some analyses. Using the identity n = 2log2 n and thus that nc = 2clog2n, we see that 2°(logn) represents an upper bound of nc for some c. The expression represents the same bound in a different way, because the expression 0(1) represents a value that is never more than a fixed constant. Frequently we derive bounds of the form nc for c greater than 0. Such bounds are called polynomial bounds. Bounds of the form 2^n ) are called exponential bounds when 6 is a real number greater than 0. Big-0 notation has a companion called small-o notation. Big-0 notation says that one function is asymptotically no more than another. To say that one function is asymptotically less than another we use small-o notation. The difference between the big-0 and small-o notations is analogous to the difference between < and <. definition 7.5 Let / and g be functions /, g: —>7Z+. Say that /(n) = o(g(n)) if lim ^-f = 0. n->oo g[n) In other words, f(n) = o(g(n)) means that, for any real number c > 0, a number no exists, where f(n) < cg(n) for all n > uq. example 7.6 ........................... The following are easy to check. 1. y/n = o(n). 2. n — o(n log log n). 3. n log log n = o(nlogn). 4. nlogn = o(n2). 5. n2 = o(n3). However, f(n) is never o(f(n)). 7.1 MEASURING COMPLEXITY 251 ANALYZING ALGORITHMS Let's analyze the TM algorithm we gave for the language A — {Qk lk\k > 0}. We repeat the algorithm here for convenience. Mi = "On input string w. 1. Scan across the tape and reject if a 0 is found to the right of a 1. 2. Repeat if both 0s and Is remain on the tape: 3. Scan across the tape, crossing off a single 0 and a single 1. 4. If 0s still remain after all the Is have been crossed off, or if Is still remain after all the 0s have been crossed off, reject. Otherwise, if neither 0s nor Is remain on the tape, accept." To analyze Mi we consider each of its four stages separately. In stage 1, the machine scans across the tape to verify that the input is of the form 0*1*. Performing this scan uses n steps. As we mentioned earlier, we typically use n to represent the length of the input. Repositioning the head at the left-hand end of the tape uses another n steps. So the total used in this stage is 2n steps. In big-0 notation we say that this stage uses 0(n) steps. Note that we didn't mention the repositioning of the tape head in the machine description. Using asymptotic notation allows us to omit details of the machine description that affect the running time by at most a constant factor. In stages 2 and 3, the machine repeatedly scans the tape and crosses off a 0 and 1 on each scan. Each scan uses 0(n) steps. Because each scan crosses off two symbols, at most n/2 scans can occur. So the total time taken by stages 2 and 3 is (n/2)0(n) = 0(n2) steps. In stage 4 the machine makes a single scan to decide whether to accept or reject. The time taken in this stage is at most O(n). Thus the total time of Mi on an input of length n is 0(n) + 0(n2) + 0(n), or 0(n2). In other words, its running time is 0(n2), which completes the time analysis of this machine. Let's set up some notation for classifying languages according to their time requirements. definition 7.7 Let t: J\f—>7l+ be a function. Define the time complexity class, TIME(t(n)), to be the collection of all languages that are decid-able by an 0(t(n)) time Turing machine. Recall the language A = {0felfc| k > 0}. The preceding analysis shows that A 6 TIME(n2) because Mi decides A in time 0(n2) and TIME(n2) contains all languages that can be decided in 0(n2) time. 252 CHAPTER 7 / TIME COMPLEXITY Is there a machine that decides A asymptotically more quickly? In other words, is A in TIME(t(n)) for t(n) = o(n2)? We can improve the running time by crossing off two Os and two Is on every scan instead of just one because doing so cuts the number of scans by half. But that improves the running time only by a factor of 2 and doesn't affect the asymptotic running time. The following machine, Af2, uses a different method to decide A asymptotically faster. It shows that A e TIME(n log n). M2 = "On input string w: 1. Scan across the tape and reject if a 0 is found to the right of a 1. 2. Repeat as long as some Os and some Is remain on the tape: 3. Scan across the tape, checking whether the total number of Os and Is remaining is even or odd. If it is odd, reject. 4. Scan again across the tape, crossing off every other 0 starting with the first 0, and then crossing off every other 1 starting with the first 1. 5. If no Os and no Is remain on the tape, accept. Otherwise, reject." Before analyzing M2, let's verify that it actually decides A. On every scan performed in stage 4, the total number of Os remaining is cut in half and any remainder is discarded. Thus, if we started with 13 Os, after stage 4 is executed a single time only 6 Os remain. After subsequent executions of this stage, 3, then 1, and then 0 remain. This stage has the same effect on the number of Is. Now we examine the even/odd parity of the number of Os and the number of Is at each execution of stage 3. Consider again starting with 13 Os and 13 Is. The first execution of stage 3 finds an odd number of Os (because 13 is an odd number) and an odd number of Is. On subsequent executions an even number (6) occurs, then an odd number (3), and an odd number (1). We do not execute this stage on 0 Os or 0 Is because of the condition on the repeat loop specified in stage 2. For the sequence of parities found (odd, even, odd, odd) if we replace the evens with Os and the odds with Is and then reverse the sequence, we obtain 1101, the binary representation of 13, or the number of Os and Is at the beginning. The sequence of parities always gives the reverse of the binary representation. When stage 3 checks to determine that the total number of Os and Is remaining is even, it actually is checking on the agreement of the parity of the Os with the parity of the Is. If all parities agree, the binary representations of the numbers of Os and of Is agree, and so the two numbers are equal. To analyze the running time of M2, we first observe that every stage takes 0(n) time. We then determine the number of times that each is executed. Stages 1 and 5 are executed once, taking a total of 0(n) time. Stage 4 crosses off at least half the Os and Is each time it is executed, so at most 1 + log2 n iterations of the repeat loop occur before all get crossed off. Thus the total time of stages 2, 3, and 4 is (1 + log2 n)O(n), or 0(n log n). The running time of M2 is O(n) + O(nlogn) = 0(n log n). 7.1 MEASURING COMPLEXITY 253 Earlier we showed that A £ TIME(n2), but now we have a better bound— namely, A £ TIME(nlogn). This result cannot be further improved on single-tape Turing machines. In fact, any language that can be decided in o(nlogn) time on a single-tape Turing machine is regular, as Problem 7.47 asks you to show. We can decide the language A in 0(n) time (also called linear time) if the Turing machine has a second tape. The following two-tape TM M3 decides A in linear time. Machine M3 operates differently from the previous machines for A. It simply copies the Os to its second tape and then matches them against the Is. Ms = "On input string w. 1. Scan across the tape and reject if a 0 is found to the right of a 1. 2. Scan across the Os on tape 1 until the first 1. At the same time, copy the Os onto tape 2. 3. Scan across the Is on tape 1 until the end of the input. For each 1 read on tape 1, cross off a 0 on tape 2. If all Os are crossed off before all the Is are read, reject. 4. If all the Os have now been crossed off, accept. If any Os remain, reject." This machine is simple to analyze. Each of the four stages uses 0(n) steps, so the total running time is 0(n) and thus is linear. Note that this running time is the best possible because n steps are necessary just to read the input. Let's summarize what we have shown about the time complexity of A, the amount of time required for deciding A. We produced a single-tape TM Mi that decides A in 0(n2) time and a faster single tape TM M2 that decides A in O(nlogn) time. The solution to Problem 7.47 implies that no single-tape TM can do it more quickly. Then we exhibited a two-tape TM M3 that decides A in 0(n) time. Hence the time complexity of A on a single-tape TM is 0(n log n) and on a two-tape TM it is O(n). Note that the complexity of A depends on the model of computation selected. This discussion highlights an important difference between complexity theory and computability theory. In computability theory, the Church-Turing thesis implies that all reasonable models of computation are equivalent—that is, they all decide the same class of languages. In complexity theory, the choice of model affects the time complexity of languages. Languages that are decidable in, say, linear time on one model aren't necessarily decidable in linear time on another. In complexity theory, we classify computational problems according to their time complexity. But with which model do we measure time? The same language may have different time requirements on different models. Fortunately, time requirements don't differ greatly for typical deterministic models. So, if our classification system isn't very sensitive to relatively small differences in complexity, the choice of deterministic model isn't crucial. We discuss this idea further in the next several sections. 254 CHAPTER 7 / TIME COMPLEXITY COMPLEXITY RELATIONSHIPS AMONG MODELS Here we examine how the choice of computational model can affect the time complexity of languages. We consider three models: the single-tape Turing machine; the multitape Turing machine; and the nondeterministic Turing machine. theorem 7.8 Let t{n) be a function, where t(n) > n. Then every t(n) time multitape Turing machine has an equivalent 0(t2(n)) time single-tape Turing machine. proof idea The idea behind the proof of this theorem is quite simple. Recall that in Theorem 3.13 we showed how to convert any multitape TM into a single-tape TM that simulates it. Now we analyze that simulation to determine how much additional time it requires. We show that simulating each step of the multitape machine uses at most 0(t(n)) steps on the single-tape machine. Hence the total time used is 0(t2(n)) steps. proof Let M be a fc-tape TM that runs in t(n) time. We construct a single-tape TM 5 that runs in 0(t2(n)) time. Machine S operates by simulating M, as described in Theorem 3.13. To review that simulation, we recall that S uses its single tape to represent the contents on all k of M's tapes. The tapes are stored consecutively, with the positions of M's heads marked on the appropriate squares. Initially, S puts its tape into the format that represents all the tapes of M and then simulates M's steps. To simulate one step, S scans all the information stored on its tape to determine the symbols under M's tape heads. Then S makes another pass over its tape to update the tape contents and head positions. If one of M's heads moves rightward onto the previously unread portion of its tape, S must increase the amount of space allocated to this tape. It does so by shifting a portion of its own tape one cell to the right. Now we analyze this simulation. For each step of M, machine S makes two passes over the active portion of its tape. The first obtains the information necessary to determine the next move and the second carries it out. The length of the active portion of S"s tape determines how long S takes to scan it, so we must determine an upper bound on this length. To do so we take the sum of the lengths of the active portions of M's k tapes. Each of these active portions has length at most t(n) because M uses t(ri) tape cells in t(n) steps if the head moves rightward at every step and even fewer if a head ever moves leftward. Thus a scan of the active portion of S"s tape uses 0(t(n)) steps. To simulate each of M's steps, S performs two scans and possibly up to k rightward shifts. Each uses 0(t(n)) time, so the total time for S to simulate one of M's steps is 0(t(n)). Now we bound the total time used by the simulation. The initial stage, where S puts its tape into the proper format, uses 0(n) steps. Afterward, S simulates each of the t(n) steps of M, using 0(t(n)) steps, so this part of the simulation uses t(n) x 0(t(n)) = 0(t2(n)) steps. Therefore the entire simulation of M uses 7.1 MEASURING COMPLEXITY 255 0{n) + 0(t2(n)) steps. We have assumed that t(n) > n (a reasonable assumption because M could not even read the entire input in less time). Therefore the running time of S is 0(t2 (n)) and the proof is complete. Next, we consider the analogous theorem for nondeterministic single-tape Turing machines. We show that any language that is decidable on such a machine is decidable on a deterministic single-tape Turing machine that requires significantly more time. Before doing so, we must define the running time of a nondeterministic Turing machine. Recall that a nondeterministic Turing machine is a decider if all its computation branches halt on all inputs. definition 7.9 Let TV be a nondeterministic Turing machine that is a decider. The running time of N is the function /: J\f—>N, where f(n) is the maximum number of steps that N uses on any branch of its computation on any input of length n, as shown in the following figure. Deterministic Nondeterministic /(*) reject /(*) ,accept accept/reject reject figure 7.10 Measuring deterministic and nondeterministic time The definition of the running time of a nondeterministic Turing machine is not intended to correspond to any real-world computing device. Rather, it is a useful mathematical definition that assists in characterizing the complexity of an important class of computational problems, as we demonstrate shortly. 256 CHAPTER 7 / TIME COMPLEXITY theorem 7.11 Let t(n) be a function, where t(n) > n. Then every t(n) time nondeterministic single-tape Turing machine has an equivalent 2°^n^ time deterministic single-tape Turing machine. proof Let TV be a nondeterministic TM running in t(n) time. We construct a deterministic TM D that simulates N as in the proof of Theorem 3.16 by searching iV's nondeterministic computation tree. Now we analyze that simulation. On an input of length n, every branch of TV's nondeterministic computation tree has a length of at most t(n). Every node in the tree can have at most 6 children, where b is the maximum number of legal choices given by TV's transition function. Thus the total number of leaves in the tree is at most bl^n\ The simulation proceeds by exploring this tree breadth first. In other words, it visits all nodes at depth d before going on to any of the nodes at depth d + 1. The algorithm given in the proof of Theorem 3.16 inefficiently starts at the root and travels down to a node whenever it visits that node, but eliminating this inefficiency doesn't alter the statement of the current theorem, so we leave it as is. The total number of nodes in the tree is less than twice the maximum number of leaves, so we bound it by 0(6^n^). The time for starting from the root and traveling down to a node is 0(t(n)). Therefore the running time of D isO(t(n)&*(n>) = 2°Wn». As described in Theorem 3.16, the TM D has three tapes. Converting to a single-tape TM at most squares the running time, by Theorem 7.8. Thus the running time of the single-tape simulator is (2°Wn)))2 = 2G{-2t^ = 2°^\ and the theorem is proved. 7.2 .....■ ■ ■ - ■ ■ ..... - - THE CLASS P Theorems 7.8 and 7.11 illustrate an important distinction. On the one hand, we demonstrated at most a square or polynomial difference between the time complexity of problems measured on deterministic single-tape and multitape Turing machines. On the other hand, we showed at most an exponential difference between the time complexity of problems on deterministic and nondeterministic Turing machines. POLYNOMIAL TIME For our purposes, polynomial differences in running time are considered to be small, whereas exponential differences are considered to be large. Let's look at 7.2 THE CLASS P 257 why we chose to make this separation between polynomials and exponentials rather than between some other classes of functions. First, note the dramatic difference between the growth rate of typically occurring polynomials such as n3 and typically occurring exponentials such as 2n. For example, let n be 1000, the size of a reasonable input to an algorithm. In that case, n3 is 1 billion, a large, but manageable number, whereas 2n is a number much larger than the number of atoms in the universe. Polynomial time algorithms are fast enough for many purposes, but exponential time algorithms rarely are useful. Exponential time algorithms typically arise when we solve problems by exhaustively searching through a space of solutions, called brute-force search. For example, one way to factor a number into its constituent primes is to search through all potential divisors. The size of the search space is exponential, so this search uses exponential time. Sometimes, brute-force search may be avoided through a deeper understanding of a problem, which may reveal a polynomial time algorithm of greater utility. All reasonable deterministic computational models are polynomially equivalent. That is, any one of them can simulate another with only a polynomial increase in running time. When we say that all reasonable deterministic models are polynomially equivalent, we do not attempt to define reasonable. However, we have in mind a notion broad enough to include models that closely approximate running times on actual computers. For example, Theorem 7.8 shows that the deterministic single-tape and multitape Turing machine models are polynomially equivalent. From here on we focus on aspects of time complexity theory that are unaffected by polynomial differences in running time. We consider such differences to be insignificant and ignore them. Doing so allows us to develop the theory in a way that doesn't depend on the selection of a particular model of computation. Remember, our aim is to present the fundamental properties of computation, rather than properties of Turing machines or any other special model. You may feel that disregarding polynomial differences in running time is absurd. Real programmers certainly care about such differences and work hard just to make their programs run twice as quickly. However, we disregarded constant factors a while back when we introduced asymptotic notation. Now we propose to disregard the much greater polynomial differences, such as that between time n and time n3. Our decision to disregard polynomial differences doesn't imply that we consider such differences unimportant. On the contrary, we certainly do consider the difference between time n and time n3 to be an important one. But some questions, such as the polynomiality or nonpolynomiality of the factoring problem, do not depend on polynomial differences and are important, too. We merely choose to focus on this type of question here. Ignoring the trees to see the forest doesn't mean that one is more important than the other—it just gives a different perspective. Now we come to an important definition in complexity theory. 258 CHAPTER 7 / TIME COMPLEXITY definition 7.12 P is the class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine. In other words, P = ljTIME(nfc). fc The class P plays a central role in our theory and is important because 1. P is invariant for all models of computation that are polynomially equivalent to the deterministic single-tape Turing machine, and 2. P roughly corresponds to the class of problems that are realistically solvable on a computer. Item 1 indicates that P is a mathematically robust class. It isn't affected by the particulars of the model of computation that we are using. Item 2 indicates that P is relevant from a practical standpoint. When a problem is in P, we have a method of solving it that runs in time nk for some constant k. Whether this running time is practical depends on k and on the application. Of course, a running time of n100 is unlikely to be of any practical use. Nevertheless, calling polynomial time the threshold of practical solvability has proven to be useful. Once a polynomial time algorithm has been found for a problem that formerly appeared to require exponential time, some key insight into it has been gained, and further reductions in its complexity usually follow, often to the point of actual practical utility. EXAMPLES OF PROBLEMS IN P When we present a polynomial time algorithm, we give a high-level description of it without reference to features of a particular computational model. Doing so avoids tedious details of tapes and head motions. We need to follow certain conventions when describing an algorithm so that we can analyze it for polynomial! ty. We describe algorithms with numbered stages. The notion of a stage of an algorithm is analogous to a step of a Turing machine, though of course, implementing one stage of an algorithm on a Turing machine, in general, will require many Turing machine steps. When we analyze an algorithm to show that it runs in polynomial time, we need to do two things. First, we have to give a polynomial upper bound (usually in big-0 notation) on the number of stages that the algorithm uses when it runs on an input of length n. Then, we have to examine the individual stages in the description of the algorithm to be sure that each can be implemented in polynomial time on a reasonable deterministic model. We choose the stages when we describe the algorithm to make this second part of the analysis easy to 7.2 THE CLASS P 259 do. When both tasks have been completed, we can conclude that the algorithm runs in polynomial time because we have demonstrated that it runs for a polynomial number of stages, each of which can be done in polynomial time, and the composition of polynomials is a polynomial. One point that requires attention is the encoding method used for problems. We continue to use the angle-bracket notation (•} to indicate a reasonable encoding of one or more objects into a string, without specifying any particular encoding method. Now, a reasonable method is one that allows for polynomial time encoding and decoding of objects into natural internal representations or into other reasonable encodings. Familiar encoding methods for graphs, automata, and the like all are reasonable. But note that unary notation for encoding numbers (as in the number 17 encoded by the unary string 11111111111111111) isn't reasonable because it is exponentially larger than truly reasonable encodings, such as base k notation for any k > 2. Many computational problems you encounter in this chapter contain encodings of graphs. One reasonable encoding of a graph is a list of its nodes and edges. Another is the adjacency matrix, where the (i, j)th entry is 1 if there is an edge from node i to node j and 0 if not. When we analyze algorithms on graphs, the running time may be computed in terms of the number of nodes instead of the size of the graph representation. In reasonable graph representations, the size of the representation is a polynomial in the number of nodes. Thus, if we analyze an algorithm and show that its running time is polynomial (or exponential) in the number of nodes, we know that it is polynomial (or exponential) in the size of the input. The first problem concerns directed graphs. A directed graph G contains nodes s and t, as shown in the following figure. The PATH problem is to determine whether a directed path exists from s tot. Let PATH — {(G, s,t) \ G is a directed graph that has a directed path from s to t}. figure 7.13 The PATH problem: Is there a path from s to t? 260 CHAPTER 7 / TIME COMPLEXITY theorem 7.14 PATH e P. proof idea We prove this theorem by presenting a polynomial time algorithm that decides PATH. Before describing that algorithm, let's observe that a brute-force algorithm for this problem isn't fast enough. A brute-force algorithm for PATH proceeds by examining all potential paths in G and determining whether any is a directed path from s to t. A potential path is a sequence of nodes in G having a length of at most m, where m is the number of nodes in G. (If any directed path exists from s to t, one having a length of at most m exists because repeating a node never is necessary.) But the number of such potential paths is roughly mm, which is exponential in the number of nodes in G. Therefore this brute-force algorithm uses exponential time. To get a polynomial time algorithm for PATH we must do something that avoids brute force. One way is to use a graph-searching method such as breadth-first search. Here, we successively mark all nodes in G that are reachable from s by directed paths of length 1, then 2, then 3, through m. Bounding the running time of this strategy by a polynomial is easy. proof A polynomial time algorithm M for PATH operates as follows. M = "On input (G, s, t) where G is a directed graph with nodes s and t: 1. Place a mark on node s. 2. Repeat the following until no additional nodes are marked: 3. Scan all the edges of G. If an edge (a, b) is found going from a marked node a to an unmarked node b, mark node 6. 4. If t is marked, accept. Otherwise, reject." Now we analyze this algorithm to show that it runs in polynomial time. Obviously, stages 1 and 4 are executed only once. Stage 3 runs at most m times because each time except the last it marks an additional node in G. Thus the total number of stages used is at most 1 + 1 + m, giving a polynomial in the size of G. Stages 1 and 4 of M are easily implemented in polynomial time on any reasonable deterministic model. Stage 3 involves a scan of the input and a test of whether certain nodes are marked, which also is easily implemented in polynomial time. Hence M is a polynomial time algorithm for PATH. Let's turn to another example of a polynomial time algorithm. Say that two numbers are relatively prime if 1 is the largest integer that evenly divides them both. For example, 10 and 21 are relatively prime, even though neither of them is a prime number by itself, whereas 10 and 22 are not relatively prime because both are divisible by 2. Let RELPRIME be the problem of testing whether two 7.2 THE CLASS P 261 numbers are relatively prime. Thus RELPRIME = {{x,y)\ x and y are relatively prime}. theorem 7.15 ......................................................................................................................... RELPRIME e P. proof idea One algorithm that solves this problem searches through all possible divisors of both numbers and accepts if none are greater than 1. However, the magnitude of a number represented in binary, or in any other base k notation for k > 2, is exponential in the length of its representation. Therefore this brute-force algorithm searches through an exponential number of potential divisors and has an exponential running time. Instead, we solve this problem with an ancient numerical procedure, called the Euclidean algorithm, for computing the greatest common divisor. The greatest common divisor of natural numbers x and y, written gcd(a\ y), is the largest integer that evenly divides both x and y. For example, gcd(18, 24) = 6. Obviously, x and y are relatively prime iff gcd(a;, y) = 1. We describe the Euclidean algorithm as algorithm E in the proof. It uses the mod function, where x mod y is the remainder after the integer division of x by y. proof The Euclidean algorithm E is as follows. E = "On input (x, y), where x and y are natural numbers in binary: 1. Repeat until y = 0: 2. Assign x <— x mod y. 3. Exchange x and y. 4. Output x." Algorithm R solves RELPRIME, using E as a subroutine. R = "On input (x, y), where x and y are natural numbers in binary: 1. Run E on (x, y). 2. If the result is 1, accept. Otherwise, reject." Clearly, if E runs correctly in polynomial time, so does R and hence we only need to analyze E for time and correctness. The correctness of this algorithm is well known so we won't discuss it further here. To analyze the time complexity of E, we first show that every execution of stage 2 (except possibly the first), cuts the value of x by at least half. After stage 2 is executed, x < y because of the nature of the mod function. After stage 3, x > y because the two have been exchanged. Thus, when stage 2 is subsequently executed, x > y. If x/2 > y, then x mod y < y < x/2 and x drops by at least half. If x/2 < y, then x mod y — x — y < x/2 and x drops by at least half. 262 CHAPTER 7 / TIME COMPLEXITY The values of x and y are exchanged every time stage 3 is executed, so each of the original values of x and y are reduced by at least half every other time through the loop. Thus the maximum number of times that stages 2 and 3 are executed is the lesser of 2 log2 x and 2 log2 y. These logarithms are proportional to the lengths of the representations, giving the number of stages executed as 0(n). Each stage of E uses only polynomial time, so the total running time is polynomial. The final example of a polynomial time algorithm shows that every context-free language is decidable in polynomial time. theorem 7.16 Every context-free language is a member of P. proof idea In Theorem 4.9 we proved that every CFL is decidable. To do so we gave an algorithm for each CFL that decides it. If that algorithm runs in polynomial time, the current theorem follows as a corollary. Let's recall that algorithm and find out whether it runs quickly enough. Let L be a CFL generated by CFG G that is in Chomsky normal form. From Problem 2.26, any derivation of a string w has 2n — 1 steps, where n is the length of w because G is in Chomsky normal form. The decider for L works by trying all possible derivations with 2n — 1 steps when its input is a string of length n. If any of these is a derivation of w, the decider accepts; if not, it rejects. A quick analysis of this algorithm shows that it doesn't run in polynomial time. The number of derivations with k steps may be exponential in k, so this algorithm may require exponential time. To get a polynomial time algorithm we introduce a powerful technique called dynamic programming. This technique uses the accumulation of information about smaller subproblems to solve larger problems. We record the solution to any subproblem so that we need to solve it only once. We do so by making a table of all subproblems and entering their solutions systematically as we find them. In this case, we consider the subproblems of determining whether each variable in G generates each substring of w. The algorithm enters the solution to this subproblem in an n x n table. For i < j the (i, j)th entry of the table contains the collection of variables that generate the substring WiWi+i • ■ -Wj. For i > j the table entries are unused. The algorithm fills in the table entries for each substring of w. First it fills in the entries for the substrings of length 1, then those of length 2, and so on. It uses the entries for the shorter lengths to assist in determining the entries for the longer lengths. 7.2 THE CLASS P 263 For example, suppose that the algorithm has already determined which variables generate all substrings up to length k. To determine whether a variable A generates a particular substring of length k + 1 the algorithm splits that substring into two nonempty pieces in the k possible ways. For each split, the algorithm examines each rule A —> BC to determine whether B generates the first piece and C generates the second piece, using table entries previously computed. If both B and C generate the respective pieces, A generates the substring and so is added to the associated table entry. The algorithm starts the process with the strings of length 1 by examining the table for the rules A —> b. proof The following algorithm D implements the proof idea. Let G be a CFG in Chomsky normal form generating the CFL L. Assume that S is the start variable. (Recall that the empty string is handled specially in a Chomsky normal form grammar. The algorithm handles the special case in which w = e in stage 1.) Comments appear inside double brackets. D = "On input w = w\ ■ ■ ■ wn: 1. If w — e and S —» e is a rule, accept. [handle w = e case] 2. For i = 1 to n: [ examine each substring of length 1 ] 3. For each variable A: 4. Test whether A —>• b is a rule, where b = W{. 5. If so, place A in table(i, i). 6. For / = 2 to n: [ / is the length of the substring] 7. For i = 1 to n — Z + 1: [ i is the start position of the substring] 8. Let j = i + I — 1, [ j is the end position of the substring] 9. For k = i to j — 1: [ k is the split position] 10. For each rule A —»• BC: 11. If table(i,k) contains B and table(k + contains C, put A in table 12. If 5 is in table(1, n), accept. Otherwise, reject." Now we analyze D. Each stage is easily implemented to run in polynomial time. Stages 4 and 5 run at most nv times, where v is the number of variables in G and is a fixed constant independent of n; hence these stages run 0{n) times. Stage 6 runs at most n times. Each time stage 6 runs, stage 7 runs at most n times. Each time stage 7 runs, stages 8 and 9 run at most n times. Each time stage 9 runs, stage 10 runs r times, where r is the number of rules of G and is another fixed constant. Thus stage 11, the inner loop of the algorithm, runs 0(n3) times. Summing the total shows that D executes 0(n3) stages. 264 CHAPTER 7 / TIME COMPLEXITY 7.3 THE CLASS NP As we observed in Section 7.2, we can avoid brute-force search in many problems and obtain polynomial time solutions. However, attempts to avoid brute force in certain other problems, including many interesting and useful ones, haven't been successful, and polynomial time algorithms that solve them aren't known to exist. Why have we been unsuccessful in finding polynomial time algorithms for these problems? We don't know the answer to this important question. Perhaps these problems have, as yet undiscovered, polynomial time algorithms that rest on unknown principles. Or possibly some of these problems simply cannot be solved in polynomial time. They may be intrinsically difficult. One remarkable discovery concerning this question shows that the complexities of many problems are linked. A polynomial time algorithm for one such problem can be used to solve an entire class of problems. To understand this phenomenon, let's begin with an example. KHamiltonian path in a directed graph G is a directed path that goes through each node exactly once. We consider the problem of testing whether a directed graph contains a Hamiltonian path connecting two specified nodes, as shown in the following figure. Let HAMPATH = {{G, s, t) \ G is a directed graph with a Hamiltonian path from s to t}. figure 7.17 A Hamiltonian path goes through every node exactly once We can easily obtain an exponential time algorithm for the HAMPATH problem by modifying the brute-force algorithm for PATH given in Theorem 7.14. We need only add a check to verify that the potential path is Hamiltonian. No one knows whether HAMPATH is solvable in polynomial time. The HAMPATH problem does have a feature called polynomial verifiabil- 7.3 THE CLASS NP 265 ity that is important for understanding its complexity. Even though we don't know of a fast (i.e., polynomial time) way to determine whether a graph contains a Hamiltonian path, if such a path were discovered somehow (perhaps using the exponential time algorithm), we could easily convince someone else of its existence, simply by presenting it. In other words, verifying the existence of a Hamiltonian path may be much easier than determining its existence. Another polynomially verifiable problem is compositeness. Recall that a natural number is composite if it is the product of two integers greater than 1 (i.e., a composite number is one that is not a prime number). Let COMPOSITES = {x\x=pq, for integers p, q > 1}. We can easily verify that a number is composite—all that is needed is a divisor of that number. Recently, a polynomial time algorithm for testing whether a number is prime or composite was discovered, but it is considerably more complicated than the preceding method for verifying compositeness. Some problems may not be polynomially verifiable. For example, take HAMPATH, the complement of the HAMPATH problem. Even if we could determine (somehow) that a graph did not have a Hamiltonian path, we don't know of a way for someone else to verify its nonexistence without using the same exponential time algorithm for making the determination in the first place. A formal definition follows. definition 7.18 A verifier for a language A is an algorithm V, where A — {w\ V accepts (w, c) for some string c}. We measure the time of a verifier only in terms of the length of w, so a polynomial time verifier runs in polynomial time in the length of w. A language A is polynomially verifiable if it has a polynomial time verifier. A verifier uses additional information, represented by the symbol c in Definition 7.18, to verify that a string w is a member of A. This information is called a certificate, or proof, of membership in A. Observe that, for polynomial verifiers, the certificate has polynomial length (in the length of w) because that is all the verifier can access in its time bound. Let's apply this definition to the languages HAMPATH and COMPOSITES. For the HAMPATH problem, a certificate for a string (G, s, t) e HAMPATH simply is the Hamiltonian path from s to t. For the COMPOSITES problem, a certificate for the composite number x simply is one of its divisors. In both cases the verifier can check in polynomial time that the input is in the language when it is given the certificate. 266 CHAPTER 7 / TIME COMPLEXITY definition 7.19 NP is the class of languages that have polynomial time verifiers. The class NP is important because it contains many problems of practical interest. From the preceding discussion, both HAMPATH and COMPOSITES are members of NP. As we mentioned, COMPOSITES is also a member of P which is a subset of NP, but proving this stronger result is much more difficult. The term NP comes from nondeterministic polynomial time and is derived from an alternative characterization by using nondeterministic polynomial time Turing machines. Problems in NP are sometimes called NP-problems. The following is a nondeterministic Turing machine (NTM) that decides the HAMPATH problem in nondeterministic polynomial time. Recall that in Definition 7.9 we defined the time of a nondeterministic machine to be the time used by the longest computation branch. N\ = "On input (G, s, t), where G is a directed graph with nodes s and t: 1. Write a list of m numbers, pi, ...,pm, where m is the number of nodes in G. Each number in the list is nondeterministically selected to be between 1 and m. 2. Check for repetitions in the list. If any are found, reject. 3. Check whether s = p\ and t = pm. If either fail, reject. 4. For each i between 1 and m — 1, check whether (pi,Pi+i) is an edge of G. If any are not, reject. Otherwise, all tests have been passed, so accept." To analyze this algorithm and verify that it runs in nondeterministic polynomial time, we examine each of its stages. In stage 1, the nondeterministic selection clearly runs in polynomial time. In stages 2 and 3, each part is a simple check, so together they run in polynomial time. Finally, stage 4 also clearly runs in polynomial time. Thus this algorithm runs in nondeterministic polynomial time. theorem 7.20 A language is in NP iff it is decided by some nondeterministic polynomial time Turing machine. proof idea We show how to convert a polynomial time verifier to an equivalent polynomial time NTM and vice versa. The NTM simulates the verifier by guessing the certificate. The verifier simulates the NTM by using the accepting branch as the certificate. proof For the forward direction of this theorem, let A 6 NP and show that A is decided by a polynomial time NTM N. Let V be the polynomial time verifier for A that exists by the definition of NP. Assume that V is a TM that runs in time nk and construct N as follows. 7.3 THE CLASS NP 267 N = "On input w of length n: 1. Nondeterministically select string c of length at most nk. 2. Run V on input (w,c). 3. IfV accepts, accept; otherwise, reject." To prove the other direction of the theorem, assume that A is decided by a polynomial time NTM N and construct a polynomial time verifier V as follows. V = "On input (w, c), where w and c are strings: 1. Simulate N on input w, treating each symbol of c as a description of the nondeterministic choice to make at each step (as in the proof of Theorem 3.16). 2. If this branch of A^'s computation accepts, accept; otherwise, reject." We define the nondeterministic time complexity class NTIME(£(n)) as analogous to the deterministic time complexity class TIME (t(n)). definition 7.21 NTIME(t(n)) = {L\ L is a language decided by a 0{t(n)) time nondeterministic Turing machine}. corollary 7.22 ................................................................................................................... NP = UfcNTIME(nfc). The class NP is insensitive to the choice of reasonable nondeterministic computational model because all such models are polynomially equivalent. When describing and analyzing nondeterministic polynomial time algorithms, we follow the preceding conventions for deterministic polynomial time algorithms. Each stage of a nondeterministic polynomial time algorithm must have an obvious implementation in nondeterministic polynomial time on a reasonable non-deterministic computational model. We analyze the algorithm to show that every branch uses at most polynomially many stages. EXAMPLES OF PROBLEMS IN NP A clique in an undirected graph is a subgraph, wherein every two nodes are connected by an edge. A k-clique is a clique that contains k nodes. Figure 7.23 illustrates a graph having a 5-clique 268 CHAPTER 7 / TIME COMPLEXITY figure 7.23 A graph with a 5-clique The clique problem is to determine whether a graph contains a clique of a specified size. Let CLIQUE — {(G, k)\ G is an undirected graph with a /e-clique}. theorem 7.24 ......................................................................................................................... CLIQUE is in NP. proof idea The clique is the certificate. proof The following is a verifier V for CLIQUE. V = "On input ((G,k),c): 1. Test whether c is a set of k nodes in G 2. Test whether G contains all edges connecting nodes in c. 3. If both pass, accept; otherwise, reject." alternative proof If you prefer to think of NP in terms of nonde-terministic polynomial time Turing machines, you may prove this theorem by giving one that decides CLIQUE. Observe the similarity between the two proofs. N — "On input (G, k), where G is a graph: 1. Nondeterministically select a subset c of k nodes of G. 2. Test whether G contains all edges connecting nodes in c. 3. If yes, accept; otherwise, reject." Next we consider the SUBSET-SUM problem concerning integer arithmetic. In this problem we have a collection of numbers xi, ..., Xfc and a target number t. We want to determine whether the collection contains a subcollection that 7.3 THE CLASS NP 269 adds up to t. Thus SUBSET-SUM = {(S, t)\ S = {xu ..., xk} and for some {yi, ■■-,yi} C • ■ -,Xk}, we have = t}. For example, {{4,11,16,21,27}, 25) € SUBSET-SUM because 4 + 21 = 25. Note that {xi, ...,x/~} and {yi, ... ,yi} are considered to be multisets and so allow repetition of elements. theorem 7.25 ......................................................................................................................... SUBSET-SUM is in NP. proof idea The subset is the certificate. proof The following is a verifier V for SUBSET-SUM. ^ = "On input ((5, t),c): 1. Test whether c is a collection of numbers that sum to t. 2. Test whether S contains all the numbers in c. 3. If both pass, accept; otherwise, reject." alternative proof We can also prove this theorem by giving a nonde-terministic polynomial time Turing machine for SUBSET-SUM as follows. N = "On input (S, t): 1. Nondeterministically select a subset c of the numbers in S. 2. Test whether c is a collection of numbers that sum to t. 3. If the test passes, accept; otherwise, reject." Observe that the complements of these sets, CLIQUE and SUBSET-SUM, are not obviously members of NP. Verifying that something is not present seems to be more difficult than verifying that it is present. We make a separate complexity class, called coNP, which contains the languages that are complements of languages in NP. We don't know whether coNP is different from NP. THE P VERSUS NP QUESTION As we have been saying, NP is the class of languages that are solvable in polynomial time on a nondeterministic Turing machine, or, equivalently, it is the class of languages whereby membership in the language can be verified in polynomial time. P is the class of languages where membership can be tested in polynomial time. We summarize this information as follows, where we loosely refer to 270 CHAPTER 7 / TIME COMPLEXITY polynomial time solvable as solvable "quickly." P = the class of languages for which membership can be decided quickly. NP = the class of languages for which membership can be verified quickly. We have presented examples of languages, such as HAMPATH and CLIQUE, that are members of NP but that are not known to be in P. The power of polynomial verifiability seems to be much greater than that of polynomial decidability. But, hard as it may be to imagine, P and NP could be equal. We are unable to prove the existence of a single language in NP that is not in P. The question of whether P = NP is one of the greatest unsolved problems in theoretical computer science and contemporary mathematics. If these classes were equal, any polynomially verifiable problem would be polynomially decid-able. Most researchers believe that the two classes are not equal because people have invested enormous effort to find polynomial time algorithms for certain problems in NP, without success. Researchers also have tried proving that the classes are unequal, but that would entail showing that no fast algorithm exists to replace brute-force search. Doing so is presently beyond scientific reach. The following figure shows the two possibilities. figure 7.26 One of these two possibilities is correct The best method known for solving languages in NP deterministically uses exponential time. In other words, we can prove that NP C EXPTIME = |J TIME(2nfe), k but we don't know whether NP is contained in a smaller deterministic time complexity class. 7.4 NP-COMPLETENESS 271 7.4 NP-COMPLETENESS One important advance on the P versus NP question came in the early 1970s with the work of Stephen Cook and Leonid Levin. They discovered certain problems in NP whose individual complexity is related to that of the entire class. If a polynomial time algorithm exists for any of these problems, all problems in NP would be polynomial time solvable. These problems are called NP-complete. The phenomenon of NP-completeness is important for both theoretical and practical reasons. On the theoretical side, a researcher trying to show that P is unequal to NP may focus on an NP-complete problem. If any problem in NP requires more than polynomial time, an NP-complete one does. Furthermore, a researcher attempting to prove that P equals NP only needs to find a polynomial time algorithm for an NP-complete problem to achieve this goal. On the practical side, the phenomenon of NP-completeness may prevent wasting time searching for a nonexistent polynomial time algorithm to solve a particular problem. Even though we may not have the necessary mathematics to prove that the problem is unsolvable in polynomial time, we believe that P is unequal to NP, so proving that a problem is NP-complete is strong evidence of its nonpolynomiality. The first NP-complete problem that we present is called the satisfiability problem. Recall that variables that can take on the values TRUE and FALSE are called Boolean variables (see Section 0.2). Usually, we represent TRUE by 1 and FALSE by 0. The Boolean operations AND, OR, and NOT, represented by the symbols A, V, and -i, respectively, are described in the following list. We use the overbar as a shorthand for the -i symbol, so x means -> x. A Boolean formula is an expression involving Boolean variables and operations. For example, is a Boolean formula. A Boolean formula is satisfiable if some assignment of 0s and Is to the variables makes the formula evaluate to 1. The preceding formula is satisfiable because the assignment x = 0, y = 1, and z = 0 makes (f> evaluate to 1. We say the assignment satisfies (p. The satisfiability problem is to test whether a Boolean formula is satisfiable. Let 0 AO = 0 0 A 1 = 0 1 A0 = 0 1 A 1 = 1 0 V0 = 0 0 V 1 = 1 1 V0 = 1 1 V 1 = 1 0 = 1 1 = 0 = (x Ay) V (x A z) SAT = {((j>)\ (fr is a satisfiable Boolean formula}. Now we state the Cook-Levin theorem, which links the complexity of the SAT problem to the complexities of all problems in NP. 272 CHAPTER 7 / TIME COMPLEXITY THEOREM 7.27 Cook-Levin theorem SAT e P iff P = NP. Next, we develop the method that is central to the proof of the Cook-Levin theorem. POLYNOMIAL TIME REDUCTIBILITY In Chapter 5 we defined the concept of reducing one problem to another. When problem A reduces to problem B, a solution to B can be used to solve A. Now we define a version of reducibility that takes the efficiency of computation into account. When problem A is efficiently reducible to problem B, an efficient solution to B can be used to solve A efficiently. DEFINITION 7.28 A function /: E* —> S* is a polynomial time computable function if some polynomial time Turing machine M exists that halts with just f(w) on its tape, when started on any input w. DEFINITION 7.29 Language A is polynomial time mapping reducible,1 or simply polynomial time reducible, to language B, written A

E* exists, where for every w, w e A 4=^ f(w) G B. The function / is called the polynomial time reduction of A to B. Polynomial time reducibility is the efficient analog to mapping reducibility as defined in Section 5.3. Other forms of efficient reducibility are available, but polynomial time reducibility is a simple form that is adequate for our purposes so we won't discuss the others here. The following figure illustrates polynomial time reducibility. It is called polynomial time many-one reducibility in some other textbooks. 7.4 NP-C COMPLETENESS 273 /1b\ / 1 \ / • • figure 7.30 Polynomial time function / reducing A to B As with an ordinary mapping reduction, a polynomial time reduction of A to B provides a way to convert membership testing in A to membership testing in B, but now the conversion is done efficiently. To test whether w £ A, we use the reduction / to map w to f(w) and test whether f(w) £ J5. If one language is polynomial time reducible to a language already known to have a polynomial time solution, we obtain a polynomial time solution to the original language, as in the following theorem. theorem 7.31 If A

) | <^ is a satisfiable 3cnf-formula}. In a satisfiable cnf-formula, each clause must contain at least one literal that is assigned 1. The following theorem presents a polynomial time reduction from the 3SAT problem to the CLIQUE problem. theorem 7.32 ...................................................... 3SAT is polynomial time reducible to CLIQUE. proof idea The polynomial time reduction / that we demonstrate from 3SAT to CLIQUE converts formulas to graphs. In the constructed graphs, cliques of a specified size correspond to satisfying assignments of the formula. Structures within the graph are designed to mimic the behavior of the variables and clauses. proof Let = (ai V b\ V ci) A (a2 V b2 V c2) A • • • A (afc V bk V ck). The reduction / generates the string (G, k), where G is an undirected graph defined as follows. The nodes in G are organized into k groups of three nodes each called the triples, £1, ..., £fc. Each triple corresponds to one of the clauses in cfi, and each node in a triple corresponds to a literal in the associated clause. Label each node of G with its corresponding literal in cf>. The edges of G connect all but two types of pairs of nodes in G. No edge is present between nodes in the same triple and no edge is present between two nodes with contradictory labels, as in x2 and x~2. The following figure illustrates this construction when 0 = (xi V x\ V x2) A (xT V xi" V X2) A (xT V x2 V x2). 7.4 NP-C COMPLETENESS 275 figure 7.33 The graph that the reduction produces from c6 = {x\ V X\ V X2) A (iT V 12 V X2) A (xiV x2V X2) Now we demonstrate why this construction works. We show that 0 is satisfi-able iff G has a fc-clique. Suppose that has a satisfying assignment. In that satisfying assignment, at least one literal is true in every clause. In each triple of G, we select one node corresponding to a true literal in the satisfying assignment. If more than one literal is true in a particular clause, we choose one of the true literals arbitrarily. The nodes just selected form a ^-clique. The number of nodes selected is k, because we chose one for each of the k triples. Each pair of selected nodes is joined by an edge because no pair fits one of the exceptions described previously. They could not be from the same triple because we selected only one node per triple. They could not have contradictory labels because the associated literals were both true in the satisfying assignment. Therefore G contains a fc-clique. Suppose that G has a fc-clique. No two of the clique's nodes occur in the same triple because nodes in the same triple aren't connected by edges. Therefore each of the k triples contains exactly one of the k clique nodes. We assign truth values to the variables of (j> so that each literal labeling a clique node is made true. Doing so is always possible because two nodes labeled in a contradictory way are not connected by an edge and hence both can't be in the clique. This assignment to the variables satisfies (ft because each triple contains a clique node and hence each clause contains a literal that is assigned TRUE. Therefore (j> is satisfiable. Theorems 7.31 and 7.32 tell us that, if CLIQUE is solvable in polynomial time, so is 3SAT. At first glance, this connection between these two problems appears quite remarkable because, superficially, they are rather different. But polynomial time reducibility allows us to link their complexities. Now we turn to a definition that will allow us similarly to link the complexities of an entire class of problems. 276 CHAPTER 7 / TIME COMPLEXITY DEFINITION OF NP-COMPLETENESS definition 7.34 A language B is NP-complete if it satisfies two conditions: 1. B is in NP, and 2. every A in NP is polynomial time reducible to B. theorem 7.35 If B is NP-complete and B eP, then P = NP. proof This theorem follows directly from the definition of polynomial time reducibility. theorem 7.36 If B is NP-complete and B

is satisfiable. Actually constructing the reduction to work in this way is a conceptually simple task, though we must cope with many details. A Boolean formula may contain the Boolean operations AND, OR, and NOT, and these operations form the basis for the circuitry used in electronic computers. Hence the fact that we can design a Boolean formula to simulate a Turing machine isn't surprising. The details are in the implementation of this idea. proof First, we show that SAT is in NP. A nondeterministic polynomial time machine can guess an assignment to a given formula and accept if the assignment satisfies . Next, we take any language A in NP and show that A is polynomial time reducible to SAT. Let N be a nondeterministic Turing machine that decides A in nk time for some constant k. (For convenience we actually assume that N runs in time nk — 3, but only those readers interested in details should worry about this minor point.) The following notion helps to describe the reduction. A tableau for N on w is an nk x nk table whose rows are the configurations of a branch of the computation of N on input w, as shown in the following figure. w1 w2 start configuration second configuration window nfcth configuration figure 7.38 A tableau is an nk x nk table of configurations 278 CHAPTER 7 / TIME COMPLEXITY For convenience later we assume that each configuration starts and ends with a # symbol, so the first and last columns of a tableau are all #s. The first row of the tableau is the starting configuration of N on w, and each row follows the previous one according to TV's transition function. A tableau is accepting if any row of the tableau is an accepting configuration. Every accepting tableau for N on w corresponds to an accepting computation branch of iV on t«. Thus the problem of determining whether N accepts w is equivalent to the problem of determining whether an accepting tableau for N on w exists. Now we get to the description of the polynomial time reduction / from A to SAT. On input w, the reduction produces a formula (j). We begin by describing the variables of 0. Say that Q and Y are the state set and tape alphabet of N. Let C = QUTU {#}. por eacn i an{f j between 1 and nk and for each s in C we have a variable, XijtS. Each of the (nk)2 entries of a tableau is called a cell. The cell in row i and column j is called cell[i,j] and contains a symbol from C. We represent the contents of the cells with the variables of 0. If XijjS takes on the value 1, it means that cell[i,j] contains an s. Now we design

s on corresponds to placing symbol s in cell[i, j]. The first thing we must guarantee in order to obtain a correspondence between an assignment and a tableau is that the assignment turns on exactly one variable for each cell. Formula 0ceu ensures this requirement by expressing it in terms of Boolean operations: cell= A (VX^>) A ( A (XiJ^VXiJj)) lceu inside the brackets stipulates that at least one variable that is associated to each cell is on, whereas the second part stipulates that no more than one variable is on for each cell. Any assignment to the variables that satisfies (p (and therefore ceii) must have exactly one variable on for every cell. Thus any satisfying assignment specifies one symbol in each cell of the table. Parts <^start5 <^movej and ^accept ensure that these symbols actually correspond to an accepting tableau as follows. Formula 0start ensures that the first row of the table is the starting configuration of N on w by explicitly stipulating that the corresponding variables are on: 0start = #1,1,# A Xli2,q0A Xl,3,Wl A Xi,4,»2 A ... A Xi)n+2,u>n A #1,71+3,1-1 A ... A xlnk_1^u A #iinfe5# . Formula accept guarantees that an accepting configuration occurs in the tableau. It ensures that gacCept, the symbol for the accept state, appears in one of the cells of the tableau, by stipulating that one of the corresponding variables is on: ^accept = \J xi,j,accept ' lmove guarantees that each row of the table corresponds to a configuration that legally follows the preceding row's configuration according to AT's rules. It does so by ensuring that each 2x3 window of cells is legal. We say that a 2 x 3 window is legal if that window does not violate the actions specified by Af's transition function. In other words, a window is legal if it might appear when one configuration correctly follows another.^ For example, say that a, b, and c are members of the tape alphabet and q\ and Q2 are states of N. Assume that, when in state qi with the head reading an a, N writes a b, stays in state qi and moves right, and that when in state qi with the head reading a b, A" nondeterministically either 1. writes a c, enters q2 and moves to the left, or 2. writes an a, enters q2 and moves to the right. Expressed formally, 5(gi,a) = {(gi,b,R)} and S(q1,b) — {(g2,c,L), (g2,a,R)}. Examples of legal windows for this machine are shown in Figure 7.39. ^ We could give a precise definition of legal window here, in terms of the transition function. But doing so is quite tedious and would distract us from the main thrust of the proof argument. Anyone desiring more precision should refer to the related analysis in the proof of Theorem 5.15, the undecidability of the Post Correspondence Problem. 280 CHAPTER 7 / TIME COMPLEXITY (a) (d) a 91 b a c # b a # b a (b) (e) a 9i b a a 92 a b a a b 92 (c) (0 a a 9i a a b b b b c b b figure 7.39 Examples of legal windows In Figure 7.39, windows (a) and (b) are legal because the transition function allows TV to move in the indicated way. Window (c) is legal because, with qi appearing on the right side of the top row, we don't know what symbol the head is over. That symbol could be an a, and q\ might change it to a b and move to the right. That possibility would give rise to this window, so it doesn't violate iV's rules. Window (d) is obviously legal because the top and bottom are identical, which would occur if the head weren't adjacent to the location of the window. Note that # may appear on the left or right of both the top and bottom rows in a legal window. Window (e) is legal because state qi reading a b might have been immediately to the right of the top row, and it would then have moved to the left in state q>2 to appear on the right-hand end of the bottom row. Finally, window (f) is legal because state qi might have been immediately to the left of the top row and it might have changed the b to a c and moved to the left. The windows shown in the following figure aren't legal for machine N. (a) (b) a 9i b 9i a a (c) b 91 b 92 b 92 figure 7.40 Examples of illegal windows In window (a) the central symbol in the top row can't change because a state wasn't adjacent to it. Window (b) isn't legal because the transition function specifies that the b gets changed to a c but not to an a. Window (c) isn't legal because two states appear in the bottom row. claim 7.41 .................................................................................................................................. If the top row of the table is the start configuration and every window in the table is legal, each row of the table is a configuration that legally follows the preceding one. 7.4 NP-C COMPLETENESS 281 We prove this claim by considering any two adjacent configurations in the table, called the upper configuration and the lower configuration. In the upper configuration, every cell that isn't adjacent to a state symbol and that doesn't contain the boundary symbol #, is the center top cell in a window whose top row contains no states. Therefore that symbol must appear unchanged in the center bottom of the window. Hence it appears in the same position in the bottom configuration. The window containing the state symbol in the center top cell guarantees that the corresponding three positions are updated consistently with the transition function. Therefore, if the upper configuration is a legal configuration, so is the lower configuration, and the lower one follows the upper one according to TV's rules. Note that this proof, though straightforward, depends crucially on our choice of a 2 x 3 window size, as Exercise 7.39 shows. Now we return to the construction of move • It stipulates that all the windows in the tableau are legal. Each window contains six cells, which may be set in a fixed number of ways to yield a legal window. Formula 0move says that the settings of those six cells must be one of these ways, or 0move = /\ (the window is legal) l. Formula ce\\ contains a fixed-size fragment of the formula for each cell of the tableau, so its size is 0(n2k). Formula 0start has a fragment for each cell in the top row, so its size is 0(nk). Formulas (pmove and accept each contain a fixed-size fragment of the formula for each cell of the tableau, so their size is 0(n2k). Thus 0's total size is 0(n2k). That bound is sufficient for our purposes because it shows that the the size of (j> is polynomial in n. If it were more than polynomial, the reduction wouldn't have any chance of generating it in polynomial time. (Actually our estimates are low by a factor of O(logn) because each variable has indices that can range up to nk and so may require O(logn) symbols to write into the formula, but this additional factor doesn't change the polynomiality of the result.) To see that we can generate the formula in polynomial time, observe its highly repetitive nature. Each component of the formula is composed of many nearly 282 CHAPTER 7 / TIME COMPLEXITY identical fragments, which differ only at the indices in a simple way. Therefore we may easily construct a reduction that produces in polynomial time from the input w. Thus we have concluded the proof of the Cook-Levin theorem, showing that SAT is NP-complete. Showing the NP-completeness of other languages generally doesn't require such a lengthy proof. Instead NP-completeness can be proved with a polynomial time reduction from a language that is already known to be NP-complete. We can use SAT for this purpose, but using 3SAT, the special case of SAT that we defined on page 274, is usually easier. Recall that the formulas in 3SAT are in conjunctive normal form (cnf) with three literals per clause. First, we must show that 3SAT itself is NP-complete. We prove this assertion as a corollary to Theorem 7.37. corollary 7.42 ................................................................................................................... 3SAT is NP-complete. proof Obviously 3SAT is in NP, so we only need to prove that all languages in NP reduce to 3SAT in polynomial time. One way to do so is by showing that SAT polynomial time reduces to 3SAT. Instead, we modify the proof of Theorem 7.37 so that it directly produces a formula in conjunctive normal form with three literals per clause. Theorem 7.37 produces a formula that is already almost in conjunctive normal form. Formula cen is a big AND of subformulas, each of which contains a big OR and a big AND of ORs. Thus c£ceii is an AND of clauses and so is already in cnf. Formula 0start is a big AND of variables. Taking each of these variables to be a clause of size 1 we see that c£start is in cnf. Formula accept is a big OR of variables and is thus a single clause. Formula move is a big AND of subformulas, each of which is an OR of ANDs that describes all possible legal windows. The distributive laws, as described in Chapter 0, state that we can replace an OR of ANDs with an equivalent AND of ORs. Doing so may significantly increase the size of each subformula, but it can only increase the total size of 0move by a constant factor because the size of each subformula depends only on N. The result is a formula that is in conjunctive normal form. Now that we have written the formula in cnf, we convert it to one with three literals per clause. In each clause that currently has one or two literals, we replicate one of the literals until the total number is three. In each clause that has more than three literals, we split it into several clauses and add additional variables to preserve the satisfiability or nonsatisfiability of the original. For example, we replace clause (a\ V a into a graph G and a number k, so that is satisfiable. In effect, G simulates . The graph contains gadgets that mimic the variables and clauses of the formula. Designing these gadgets requires a bit of ingenuity. For the variable gadget, we look for a structure in G that can participate in the vertex cover in either of two possible ways, corresponding to the two possible truth assignments to the variable. Two nodes connected by an edge is a structure that works, because one of these nodes must appear in the vertex cover. We arbitrarily associate TRUE and FALSE to these two nodes. For the clause gadget, we look for a structure that induces the vertex cover to include nodes in the variable gadgets corresponding to at least one true literal in the clause. The gadget contains three nodes and additional edges so that any vertex cover must include at least two of the nodes, or possibly all three. Only two nodes would be required if one of the vertex gadget nodes helps by covering an edge, as would happen if the associated literal satisfies that clause. Otherwise three nodes would be required. Finally, we chose k so that the sought-after vertex cover has one node per variable gadget and two nodes per clause gadget. proof Here are the details of a reduction from 3SAT to VERTEX-COVER that operates in polynomial time. The reduction maps a Boolean formula 0 to a graph G and a value k. For each variable x in , we produce an edge connecting two nodes. We label the two nodes in this gadget x and x. Setting x to be TRUE corresponds to selecting the left node for the vertex cover, whereas FALSE corresponds to the right node. The gadgets for the clauses are a bit more complex. Each clause gadget is a 7.5 ADDITIONAL NP-COMPLETE PROBLEMS 285 triple of three nodes that are labeled with the three literals of the clause. These three nodes are connected to each other and to the nodes in the variables gadgets that have the identical labels. Thus the total number of nodes that appear in G is 2m + 3/, where 4> has m variables and / clauses. Let kbem + 21. For example, if = {x\ V x\ V x2) A (x~i V x~2 V x~2~) A (aTf V x2 V x2), the reduction produces (G, k) from 0, where k = 8 and G takes the form shown in the following figure. figure 7.45 The graph that the reduction produces from

is satisfiable by constructing the satisfying assignment. The vertex cover must contain one node in each variable gadget and two in every clause gadget in order to cover the edges of the variable gadgets and the three edges within the clause gadgets. That accounts for all the nodes, so none are left over. We take the nodes of the variable gadgets that are in the vertex cover and assign the corresponding literals TRUE. That assignment satisfies 4> because each of the three edges connecting the variable gadgets with each clause gadget is covered and only two nodes of the clause gadget are in the vertex cover. Therefore one of the edges must be covered by a node from a variable gadget and so that assignment satisfies the corresponding clause. 286 CHAPTER 7 / TIME COMPLEXITY THE HAMILTON IAN PATH PROBLEM Recall that the Hamiltonian path problem asks whether the input graph contains a path from s to t that goes through every node exactly once. theorem 7.46 HAMPATH is NP-complete. proof idea We showed that HAMPATH is in NP in Section 7.3. To show that every NP-problem is polynomial time reducible to HAMPATH, we show that 3SAT is polynomial time reducible to HAMPATH. We give a way to convert 3 cnf-formulas to graphs in which Hamiltonian paths correspond to satisfying assignments of the formula. The graphs contain gadgets that mimic variables and clauses. The variable gadget is a diamond structure that can be traversed in either of two ways, corresponding to the two truth settings. The clause gadget is a node. Ensuring that the path goes through each clause gadget corresponds to ensuring that each clause is satisfied in the satisfying assignment. proof We previously demonstrated that HAMPATH is in NP, so all that remains to be done is to show 3SAT

we show how to construct a directed graph G with two nodes, s and t, where a Hamiltonian path exists between s and t iff is satisfiable. We start the construction with a 3 cnf-formula 0 containing k clauses: (/> = (oi V 6i V ci) A (a2 V b2 V c2) A • • • A (ak V bk V ck), where each a, b, and c is a literal xi or x~l. Let x\, ..., xi be the I variables of 4>. Now we show how to convert 0 to a graph G. The graph G that we construct has various parts to represent the variables and clauses that appear in (f). We represent each variable Xi with a diamond-shaped structure that contains a horizontal row of nodes, as shown in the following figure. Later we specify the number of nodes that appear in the horizontal row. figure 7.47 Representing the variable a diamond structure 7.5 ADDITIONAL NP-COMPLETE PROBLEMS 287 We represent each clause of 0 as a single node, as follows. figure 7.48 Representing the clause Cj as a node The following figure depicts the global structure of G. It shows all the elements of G and their relationships, except the edges that represent the relationship of the variables to the clauses that contain them. o O C2 O c3 O ck figure 7.49 The high-level structure of G 288 CHAPTER 7 / TIME COMPLEXITY Next we show how to connect the diamonds representing the variables to the nodes representing the clauses. Each diamond structure contains a horizontal row of nodes connected by edges running in both directions. The horizontal row contains 3k+ 1 nodes in addition to the two nodes on the ends belonging to the diamond. These nodes are grouped into adjacent pairs, one for each clause, with extra separator nodes next to the pairs, as shown in the following figure. figure 7.50 The horizontal nodes in a diamond structure If variable x^ appears in clause Cj, we add the following two edges from the jth pair in the ?'th diamond to the jth clause node. figure 7.51 The additional edges when clause Cj contains xi If Xi appears in clause Cj, we add two edges from the jth pair in the ith. diamond to the jth clause node, as shown in Figure 7.52. After we add all the edges corresponding to each occurrence of X{ or ~xi in each clause, the construction of G is complete. To show that this construction works, we argue that, if cj) is satisfiable, a Hamiltonian path exists from s to t and, conversely, if such a path exists, (j) is satisfiable. 7.5 ADDITIONAL NP-COMPLETE PROBLEMS 289 figure 7.52 The additional edges when clause Cj contains x~l Suppose that 0 is satisfiable. To demonstrate a Hamiltonian path from s to t, we first ignore the clause nodes. The path begins at s, goes through each diamond in turn, and ends up at t. To hit the horizontal nodes in a diamond, the path either zig-zags from left to right or zag-zigs from right to left, the satisfying assignment to 0 determines which. If Xi is assigned TRUE, the path zig-zags through the corresponding diamond. If Xi is assigned FALSE, the path zag-zigs. We show both possibilities in the following figure. zig-zag zag-zig figure 7.53 Zig-zagging and zag-zigging through a diamond, as determined by the satisfying assignment So far this path covers all the nodes in G except the clause nodes. We can easily include them by adding detours at the horizontal nodes. In each clause, we select one of the literals assigned TRUE by the satisfying assignment. If we selected xi in clause Cj, we can detour at the jth pair in the ith diamond. Doing so is possible because Xi must be TRUE, so the path zig-zags from left to right through the corresponding diamond. Hence the edges to the Cj node are in the correct order to allow a detour and return. Similarly, if we selected x~l in clause Cj, we can detour at the jth pair in the ith diamond because Xi must be FALSE, so the path zag-zigs from right to left through the corresponding diamond. Hence the edges to the Cj node again are 290 CHAPTER 7 / TIME COMPLEXITY in the correct order to allow a detour and return. (Note that each true literal in a clause provides an option of a detour to hit the clause node. As a result, if several literals in a clause are true, only one detour is taken.) Thus we have constructed the desired Hamiltonian path. For the reverse direction, if G has a Hamiltonian path from s to t, we demonstrate a satisfying assignment for (f>. If the Hamiltonian path is noi-mal—it goes through the diamonds in order from the top one to the bottom one, except for the detours to the clause nodes—we can easily obtain the satisfying assignment. If the path zig-zags through the diamond, we assign the corresponding variable TRUE, and if it zag-zigs, we assign FALSE. Because each clause node appears on the path, by observing how the detour to it is taken, we may determine which of the literals in the corresponding clause is TRUE. All that remains to be shown is that a Hamiltonian path must be normal. Normality may fail only if the path enters a clause from one diamond but returns to another, as in the following figure. figure 7.54 This situation cannot occur The path goes from node a\ to c, but instead of returning to a2 in the same diamond, it returns to b2 in a different diamond. If that occurs, either a2 or a3 must be a separator node. If a2 were a separator node, the only edges entering a2 would be from a\ and a3. If a3 were a separator node, a\ and a2 would be in the same clause pair, and hence the only edges entering a2 would be from a\, a3, and c. In either case, the path could not contain node a2. The path cannot enter a2 from c or a\ because the path goes elsewhere from these nodes. The path cannot enter a2 from a3, because a3 is the only available node that a2 points at, so the path must exit a2 via a3. Hence a Hamiltonian path must be normal. This reduction obviously operates in polynomial time and the proof is complete. 7.5 ADDITIONAL NP-COMPLETE PROBLEMS 291 Next we consider an undirected version of the Hamiltonian path problem, called UHAMPATH. To show that UHAMPATH is NP-complete we give a polynomial time reduction from the directed version of the problem. theorem 7.55 UHAMPATH is NP-complete. proof The reduction takes a directed graph G with nodes s and t and constructs an undirected graph G' with nodes s' and t'. Graph G has a Hamiltonian path from s to t iff G' has a Hamiltonian path from s' to t'. We describe G' as follows. Each node u of G, except for s and t, is replaced by a triple of nodes um, wmid, and wout in G'. Nodes s and t in G are replaced by nodes sout and tm in G'. Edges of two types appear in G'. First, edges connect umid with um and wout. Second, an edge connects uout with vm if an edge goes from u to v in G. That completes the construction of G'. We can demonstrate that this construction works by showing that G has a Hamiltonian path from s to t iff G' has a Hamiltonian path from sout to tln. To show one direction, we observe that a Hamiltonian path P in G, has a corresponding Hamiltonian path P' in G;, out in mid out in mid out ^in To show the other direction, we claim that any Hamiltonian path in G' from sout to tm in G' must go from a triple of nodes to a triple of nodes, except for the start and finish, as does the path P' we just described. That would complete the proof because any such path has a corresponding Hamiltonian path in G. We prove the claim by following the path starting at node sout. Observe that the next node in the path must be uf for some i because only those nodes are connected to sout. The next node must be w™d, because no other way is available to include ufld in the Hamiltonian path. After wmld comes u°ut because that is the only other one to which «™d is connected. The next node must be Uj1 for some j because no other available node is connected to w°ut. The argument then repeats until tm is reached. THE SUBSET SUM PROBLEM Recall the SUBSET-SUM problem defined on page 269. In that problem, we were given a collection of numbers X\, ..., xk together with a target number t, and were to determine whether the collection contains a subcollection that adds up to t. We now show that this problem is NP-complete. 292 CHAPTER 7 / TIME COMPLEXITY theorem 7.56 SUBSET-SUM is NP-complete. proof idea We have already shown that SUBSET-SUM is in NP in Theorem 7.25. We prove that all languages in NP are polynomial time reducible to SUBSET-SUM by reducing the NP-complete language 3SAT to it. Given a 3cnf-formula 0 we construct an instance of the SUBSET-SUM problem that contains a subcollection summing to the target t if and only if 0 is satisfiable. Call this subcollection T. To achieve this reduction we find structures of the SUBSET-SUM problem that represent variables and clauses. The SUBSET-SUM problem instance that we construct contains numbers of large magnitude presented in decimal notation. We represent variables by pairs of numbers and clauses by certain positions in the decimal representations of the numbers. We represent variable Xi by two numbers, yi and zi. We prove that either yi or Zi must be in T for each i, which establishes the encoding for the truth value of Xi in the satisfying assignment. Each clause position contains a certain value in the target t, which imposes a requirement on the subset T. We prove that this requirement is the same as the one in the corresponding clause—namely, that one of the literals in that clause is assigned TRUE. proof We already know that SUBSET-SUM € NP, so we now show that 3SAT

. So the total time is 0(n2) easy stages. EXERCISES 7.1 Answer each part TRUE or FALSE. a. 2n = 0(n). Ad. nlogn = 0(n2). b. n2 = 0{n). e. 3n = 2°(n). Ac. n2 = 0(nlog2n). f. 22" =0(22"). 7.2 Answer each part TRUE or FALSE. a. n = o(2n). Ad. 1 = o(n). b. 2n = o(n2). e. n = o(log n Ac. 2n = o(3n). f. 1 = o(l/n). 7.3 Which of the following pairs of numbers are relatively prime? Show the calculations that led to your conclusions. a. 1274 and 10505 b. 7289 and 8029 7.4 Fill out the table described in the polynomial time algorithm for context-free language recognition from Theorem 7.16 for string w = baba and CFG G: S —> RT R—* TR|a T -» TR | b 7.5 Is the following formula satisfiable? (x Vj/) A (x\/y) A (x V y) A (xVy) 7.6 Show that P is closed under union, concatenation, and complement. PROBLEMS 295 7.7 Show that NP is closed under union and concatenation. 7.8 Let CONNECTED = {(G)\ G is a connected undirected graph}. Analyze the algorithm given on page 157 to show that this language is in P. 7.9 A triangle in an undirected graph is a 3-clique. Show that TRIANGLE G P, where TRIANGLE = {(G)\ G contains a triangle}. 7.10 Show that ALLofa is in P. 7.11 Call graphs G and H isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO — {(G, H) \ G and H are isomorphic graphs}. Show that ISO G NP. PROBLEMS 7.12 Let MODEXP = {(a, b, c, p) \ a, b, c, and p are binary integers such that ab = c (mod p)}. Show that MODEXP G P. (Note that the most obvious algorithm doesn't run in polynomial time. Hint: Try it first where 6 is a power of 2.) 7.13 A permutation on the set {1, ..., k} is a one-to-one, onto function on this set. When p is a permutation, pl means the composition of p with itself t times. Let PERM-POWER = {(p,q,t)\ p — q wherep and q are permutations on {1, ..., k} and t is a binary integer}. Show that PERM-POWER G P. (Note that the most obvious algorithm doesn't run within polynomial time. Hint: First try it where t is a power of 2). 7.14 Show that P is closed under the star operation. (Hint: Use dynamic programming. On input y = yi ■ ■ ■ yn for y» G E, build a table indicating for each i < j whether the substring yi ■ • - yj G A* for any A G P.) A7.15 Show that NP is closed under the star operation. 7.16 Let UNARY-SSUM be the subset sum problem in which all numbers are represented in unary. Why does the NP-completeness proof for SUBSET-SUM fail to show UNARY-SSUM is NP-complete? Show that UNARY-SSUM G P. 7.17 Show that, if P = NP, then every language A G P, except A = 0 and A = £*, is NP-complete. *7.18 Show that PRIMES — {m\m is a prime number in binary} G NP. (Hint: Forp > 1 the multiplicative group Z* — {x \ x is relatively prime to p and 1 < x < p} is both cyclic and of order p — 1 iff p is prime. You may use this fact without justifying it. The stronger statement PRIMES G P is now known to be true, but it is more difficult to prove.) 7.19 We generally believe that PATH is not NP-complete. Explain the reason behind this belief. Show that proving PATH is not NP-complete would prove P ^ NP. 296 CHAPTER 7 / TIME COMPLEXITY 7.20 Let G represent an undirected graph. Also let SPÄTH — {(G, a, b,k) \ G contains a simple path of length at most k from a to 6}, and LPATH = {(G, a, b,k) \ G contains a simple path of length at least k from a to b}. a. Show that SPÄTH G P. b. Show that LPATH is NP-complete. You may assume the NP-completeness of UHAMPATH, the Hamiltonian path problem for undirected graphs. 7.21 Let DOUBLE-SAT = {()| ) | 0 is a satisfiable cnf-formula where each variable appears in at most k places}. a. Show that CNF2 € P. b. Show that CNF3 is NP-complete. 7.24 Let 4> be a 3cnf-formula. An ^-assignment to the variables of 0 is one where each clause contains two literals with unequal truth values. In other words, an ^-assignment satisfies 0 without assigning three true literals in any clause. a. Show that the negation of any 7^-assignment to 0 is also an ^-assignment. b. Let ^SAT be the collection of 3cnf-formulas that have an ^-assignment. Show that we obtain a polynomial time reduction from 3SAT to ^SAT by replacing each clause a (l/i V yi V y3) with the two clauses (yi V y2 V Zi) and (zl V y3 V 6), where z% is a new variable for each clause d and b is a single additional new variable. c. Conclude that ^SAT is NP-complete. 7.25 A cut in an undirected graph is a separation of the vertices V into two disjoint subsets S and T. The size of a cut is the number of edges that have one endpoint in S and the other in T. Let MAX-CUT ={(G,k)\G has a cut of size k or more}. Show that MAX-CUT is NP-complete. You may assume the result of Problem 7.24. (Hint: Show that ^SAT

0, such that elements of S can be colored red or blue so that no Ct has all its elements colored with the same color.} Show that SET-SPLITTING is NP-complete. 7.29 Consider the following scheduling problem. You are given a list of final exams Fi,..., Fk to be scheduled, and a list of students Sj,..., Si. Each student is taking some specified subset of these exams. You must schedule these exams into slots so that no student is required to take two exams in the same slot. The problem is to determine if such a schedule exists that uses only h slots. Formulate this problem as a language and show that this language is NP-complete. 298 CHAPTER 7 / TIME COMPLEXITY 7.30 This problem is inspired by the single-player game Minesweeper, generalized to an arbitrary graph. Let G be an undirected graph, where each node either contains a single, hidden mine or is empty. The player chooses nodes, one by one. If the player chooses a node containing a mine, the player loses. If the player chooses an empty node, the player learns the number of neighboring nodes containing mines. (A neighboring node is one connected to the chosen node by an edge.). The player wins if and when all empty nodes have been so chosen. In the mine consistency problem you are given a graph G, along with numbers labeling some of G's nodes. You must determine whether a placement of mines on the remaining nodes is possible, so that any node v that is labeled m has exactly m neighboring nodes containing mines. Formulate this problem as a language and show that it is NP-complete. A7.31 In the following solitaire game, you are given an m x m board. On each of its n2 positions lies either a blue stone, a red stone, or nothing at all. You play by removing stones from the board so that each column contains only stones of a single color and each row contains at least one stone. You win if you achieve this objective. Winning may or may not be possible, depending upon the initial configuration. Let SOLITAIRE — {(G)\ G is a winnable game configuration}. Prove that SOLITAIRE is NP-complete. 7.32 Let U = {(M, x, #*) | TM M accepts input x within t steps on at least one branch}. Show that U is NP-complete. 7.33 Recall, in our discussion of the Church-Turing thesis, that we introduced the language D — {(p) | p is a polynomial in several variables having an integral root}. We stated, but didn't prove, that D is undecidable. In this problem you are to prove a different property of D—namely, that D is NP-hard. A problem is NP-hard if all problems in NP are polynomial time reducible to it, even though it may not be in NP itself. So, you must show that all problems in NP are polynomial time reducible to D. 7.34 A subset of the nodes of a graph G is a dominating set if every other node of G is adjacent to some node in the subset. Let DOMINATING-SET = {{G,k)\G has a dominating set with k nodes}. Show that it is NP-complete by giving a reduction from VERTEX-COVER. *7.35 Show that the following problem is NP-complete. You are given a set of states Q — {qo, qi,.. . , qi} and a collection of pairs {(si, n),... , (sk, rk)} where the Si are distinct strings over £ = {0, l}, and the rt are (not necessarily distinct) members of Q. Determine whether a DFA M = (Q, £, 8, go, F) exists where 8(qo, Si) — rl for each i. Here, 8(q, s) is the state that M enters after reading s, starting at state q. (Note that F is irrelevant here). *7.36 Show that if P = NP, a polynomial time algorithm exists that produces a satisfying assignment when given a satisfiable Boolean formula. (Note: The algorithm you are asked to provide computes a function, but NP contains languages, not functions. The P = NP assumption implies that SAT is in P, so testing satisfiability is solvable in polynomial time. But the assumption doesn't say how this test is done, and the test may not reveal satisfying assignments. You must show that you can find them anyway. Hint: Use the satisfiability tester repeatedly to find the assignment bit-by-bit.) PROBLEMS 299 *7.37 Show that if P = NP, you can factor integers in polynomial time. (See the note in Problem 7.36.) A*7.38 Show that if P = NP, a polynomial time algorithm exists that takes an undirected graph as input and finds a largest clique contained in that graph. (See the note in Problem 7.36.) 7.39 In the proof of the Cook-Levin theorem, a window is a 2 x 3 rectangle of cells. Show why the proof would have failed if we had used 2x2 windows instead. *7.40 Consider the algorithm MINIMIZE, which takes a DFA M as input and outputs DFA M'. MINIMIZE = "On input (M), where M = (Q, S, S, q0, A) is a DFA: 1. Remove all states of M that are unreachable from the start state. 2. Construct the following undirected graph G whose nodes are the states of M. 3. Place an edge in G connecting every accept state with every nonaccept state. Add additional edges as follows. 4. Repeat until no new edges are added to G: 5. For every pair of distinct states q and r of M and every a e S: 6. Add the edge (q, r) to G if (5(q, a), 5(r, a)) is an edge of G. 7. For each state q, let [q] be the collection of states [q] = {r £ Q\ no edge joins q and r in G}. 8. Form a new DFA M' = (Q', S, 5', q0', A') where Q' = {[o\ \ Q £ Q}, (if [q] — [r], only one of them is in Q'), 5'([q],a) — [5(q, a)}, for every q £ Q and a G S, qo = [qo], and A'= {[q]\qeA}. 9. Output (M')." a. Show that M and M' are equivalent. b. Show that M' is minimal—that is, no DFA with fewer states recognizes the same language. You may use the result of Problem 1.52 without proof. c. Show that MINIMIZE operates in polynomial time. 7.41 For a cnf-formula (f> with m variables and c clauses, show that you can construct in polynomial time an NFA with 0{cm) states that accepts all nonsatisfying assignments, represented as Boolean strings of length m. Conclude that NFAs cannot be minimized in polynomial time unless P = NP. *7.42 A 2cnf-formula is an AND of clauses, where each clause is an OR of at most two literals. Let 2SAT = {() | 0 is a satisfiable 2cnf-formula}. Show that 2SAT G P. 7.43 Modify the algorithm for context-free language recognition in the proof of Theorem 7.16 to give a polynomial time algorithm that produces a parse tree for a string, given the string and a CFG, if that grammar generates the string. 7.44 Say that two Boolean formulas are equivalent if they have the same set of variables and are true on the same set of assignments to those variables (i.e., they describe the same Boolean function). A Boolean formula is minimal if no shorter Boolean formula is equivalent to it. Let MIN-FORMULA be the collection of minimal Boolean formulas. Show that, if P = NP, then MIN-FORMULA € P. 300 CHAPTER 7 / TIME COMPLEXITY 7.45 The difference hierarchy D^P is defined recursively as a. DiP = NPand b. DtP = {A\ A = B \C for B in NP and G in Dt_iP}. (Here B \ C = B n G.) For example, a language in D2P is the difference of two NP languages. Sometimes D2P is called DP (and may be written Dp). Let Z — {(Gi, hi, G2, fo)! Gi has a £;i-clique and G2 doesn't have a fc2-clique}. Show that Z is complete for DP. In other words, show that every language in DP is polynomial time reducible to Z. *7.46 Let MAX-CLIQUE = {(G, k) | the largest clique in G is of size exactly k}. Use the result of Problem 7.45 to show that MAX-CLIQUE is DP-complete. *7.47 Let /: J\f—>Af be any function where/(n) = o(n log n). Show that TIME(/(ra)) contains only the regular languages. *7.48 Call a regular expression star-free if it does not contain any star operations. Let EQsf-rex = {(Ri S}\ R and S are equivalent star-free regular expressions}. Show that EQSF_ _REX is in coNP. Why does your argument fail for general regular expressions? *7.49 This problem investigates resolution, a method for proving the unsatisfiability of cnf-formulas. Let 0 = Gi A G2 A • • • A Cm be a formula in cnf, where the d are its clauses. Let C — {Gj| C% is a clause of 2m, then if is the graph obtained by adding j nodes to G without any additional edges, where j = 2k — m. Thus H has m + j = 2k nodes, and so G has a fc-clique iff if has a clique of size k. Therefore (G, kk) G CLIQUE iff (H) G HALF-CLIQUE. We also need to show HALF-CLIQUE G NP. The certificate is simply the clique. 7.52 First, SOLITAIRE G NP because we can verify that a solution works, in polynomial time. Second, we show that 3SAT

with m variables x\,..., xm and k clauses c\,... , c&, construct the following k x m game G. We assume that 0 has no clauses that contain both xt and ~xl because such clauses may be removed without affecting satisfiability. If Xj is in clause c3 put a blue stone in row c3, column xx. Ytx~% is in clause c3 put a red stone in row Cj, column x%. We can make the board square by repeating a row or adding a blank column as necessary without affecting solvability. We show that

) Take a satisfying assignment. If x» is true (false), remove the red (blue) stones from the corresponding column. So, stones corresponding to true literals remain. Because every clause has a true literal, every row has a stone. (<—) Take a game solution. If the red (blue) stones were removed from a column, set the corresponding variable true (false). Every row has a stone remaining, so every clause has a true literal. Therefore 4> is satisfied. 7.38 If you assume that P = NP, then CLIQUE G P, and you can test whether G contains a clique of size k in polynomial time, for any value of k. By testing whether G contains a clique of each size, from 1 to the number of nodes in G, you can determine the size t of a maximum clique in G in polynomial time. Once you know t, you can find a clique with t nodes as follows. For each node x of G, remove x and calculate the resulting maximum clique size. If the resulting size decreases, replace x and continue with the next node. If the resulting size is still t, keep x permanently removed and continue with the next node. When you have considered all nodes in this way, the remaining nodes are a i-clique.