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

5.3 Nondeterministic Polynomial Time

From Nondeterministic to Deterministic Time The Satisfiability Problem The Structure of Ex The Variables of Ex The Structure of Econfi The Structure of Einit The Structure of Erulei and Eaccept The Structure of Efollowi The 3-Satisfiability Problem The subclass NP , of the class of problems that can be solved nondeterministically in polynomial time, seems to play a central role in the investigation of intractability. By definition, NP contains the class P of those problems that can be decided deterministically in polynomial time, and by Corollary 5.3.1 the class NP is contained in the class EXPTIME of those problems that can be decided deterministically in exponential time. Moreover, by Theorem 5.2.1, P is properly contained in EXPTIME (see Figure 5.3.1).

Figure 5.3.1 A classification of the decidable problems. However, it is not known whether P is properly contained in NP and whether NP is properly contained in EXPTIME. Consequently, the importance of NP arises from the refinement that it may offer to the boundary between the tractability and intractability of problems. In particular, if it is discovered that NP is not equal to P, as is widely being conjectured, then NP is likely to provide some of the easiest problems (namely, the NP-complete problems) for proving the intractability of new problems by means of reducibility. On the other hand, if NP is discovered to equal P, then many important problems, worked on without success for several decades, will turn out to be solvable in polynomial time.

From Nondeterministic to Deterministic Time An analysis of the proof of Theorem 2.3.1 implies an exponential increase in the number of states a deterministic finite-state automaton needs for simulating a nondeterministic finite-state automaton. The following corollary implies a similar exponential increase in the number of moves that a deterministic Turing machine requires for simulating a nondeterministic Turing machine. Corollary 5.3.1 For each nondeterministic Turing transducer M1 there exists an equivalent deterministic Turing transducer M2 with the following characteristics. If M1 halts on a given input x in t moves, then M2 on such an input halts within 2ct moves, where c is some constant that depends only on M1. Moreover, in such a case M2 visits at most 2t locations on each of its auxiliary work tapes. Proof Let M1 and M2 be the Turing Transducers M1 and M2 of Theorem 4.3.1. Assume that M1 halts on input x in t steps. Then M2 needs to consider only the strings in {1, . . . , r}* whose lengths are no greater than t or t + 1, depending on whether M1 accepts or rejects x, respectively. The number of such strings is no greater than (r + 1)t+1. For each string = i1 ij in {1, . . . , r}* the Turing transducer M2 uses some number of moves linear in j to derive and to try simulating a sequence of moves of the form C C . t+1 ct Consequently, M2 needs some number of moves linear in (r + 1) t. 2 is therefore a bound on the number of moves, because v = 2log v for every positive integer value v. Similarly, for each string = i1 ij the Turing transducer M2 needs j locations in the first auxiliary work tape for storing , and at most j locations in each of the other auxiliary work tapes for recording the content of the corresponding tapes of M1. By setting the heads of the auxiliary work tapes at their initial positions before starting the simulation of M1 on , it is assured that the heads do not depart more than t locations from their initial positions. The Satisfiability Problem The following theorem shows the existence of NP-complete problems through example. Definitions A Boolean expression is an expression defined inductively in the following way.

a. The constants 0 (false) and 1 (true) are Boolean expressions. b. Each variable x is a Boolean expression. c. If E1 and E2 are Boolean expressions, then so are the negation E1, the conjunction E1 E2, the disjunction E1 E2, and the parenthesizing (E1). Each assignment of 0's and 1's to the variables of a Boolean expression provides a value to the expression. If E is a Boolean expression, then (E) has the same value as E. E has the value 0 if E has the value 1, and E has the value 1 if E has the value 0. If E1 and E2 are Boolean expressions, then E1 E2 has the value 1 whenever E1 or E2 has the value 1. E1 E2 has the value 0 whenever both E1 and E2 have the value 0. The value of E1 E2 is 1 if both E1 and E2

have the value 1, otherwise E1 E2 has the value 0. It is assumed that among the Boolean operations of , , and , the operation has the highest precedence, followed by , and then . A Boolean expression is said to be satisfiable if its variables can be assigned 0's and 1's so as to provide the value 1 to the expression. The satisfiability problem asks for any given Boolean expression whether it is satisfiable, that is, whether the instance is in the set Lsat = { E | E is a satisfiable Boolean expression }. Example 5.3.1 The Boolean expression E = x2 x3 (x1 x2) is satisfiable by each assignment in which x2 = 1 and x3 = 1, as well as by each assignment in which x1 = 0 and x2 = 1. All the other assignments provide a 0 value to E. (x2 x3) ((x1) x2) is a fully parenthesized version of E. x x is an example of an unsatisfiable Boolean expression. The proof of the following theorem uses a generic approach. Theorem 5.3.1 The satisfiability problem is NP-complete.

Proof The satisfiability of any Boolean expression can be checked in polynomial time by nondeterministically assigning some values to the variables of the given expression and then evaluating the expression for such an assignment. Consequently, the problem is in NP. To show that the satisfiability problem is NP-hard, it is sufficient to demonstrate that each problem K in NP has a polynomially time-bounded, deterministic Turing transducer TK, such that TK reduces K to the satisfiability problem. For the purpose of the proof consider any problem K in NP. Assume that M = <Q, , , , q0, B, F> is a nondeterministic Turing machine with Q ( {, $}) = that decides K in T(n) = O(nk) time. Let m denote the number of auxiliary work tapes of M; then TK can be a Turing transducer that on input x outputs a Boolean expression Ex of the following form. The Structure of Ex The Boolean expression Ex describes how an accepting computation of M on input x should look. Ex is satisfiable by a given assignment if and only if the assignment corresponds to an accepting computation C0 C1 CT(|x|) of M on input x. The expression has the following structure, where t = T(|x|).

Econf0 Econft states that an accepting computation consists of a sequence C0, . . . , Ct of t + 1 configurations. Einit states that C0 is an initial configuration. Erule1 Erulet states that an accepting computation uses a sequence of t transition rules. Eaccept states that the last transition rule in enters an accepting state. With no loss of generality it is

assumed that a transition rule can also be "null", that is, a transition rule on which M can have a move without a change in its configuration. Such an assumption allows us to restrict the consideration only to computations that consist of exactly T(|x|) moves. Efollowi states that M by using the ith transition rule in configuration Ci-1, 1 i t. The Variables of Ex The Boolean expression Ex uses variables of the form wi,r,j,X and variables of the form wi, . Each variable provides a statement about a possible property of an accepting computation. An assignment that satisfies Ex provides the value 1 to those variables whose statements hold for the computation in question, and provides the value 0 to those variables whose statements do not hold for that computation. wi,r,j,X states that X is the jth character of the rth tape in the ith configuration, 0 refers to the input tape, and 1 r m refers to the rth auxiliary work tape. wi, states that is the transition rule in the ith move of the computation. The Structure of Econfi The expression Econfi is the conjunction of the following Boolean expressions. a. { wi,0,j,X | X is in {, $} Q } for 1 j |x| + 3. r m. r = 0 reaches configuration Ci from

This expression states that a configuration has an input segment with |x| + 3 entries, with each entry having at least one symbol from {, $} Q. b. { (wi,0,j,X wi,0,j,Y ) | X and Y are in {, $} Q and X Y } for 1 j |x| + 3.

This expression states that each entry in the input segment has at most one symbol. c. { wi,r,j,X | X is in Q } for 1 r m and 1 j t + 1.

This expression states that a configuration has m auxiliary work-tape segments, each segment having t + 1 entries, and each entry having at least one symbol from Q. d. { (wi,r,j,X wi,r,j,Y ) | X and Y are in Q and X Y } for 1 r m and 1 j t + 1.

This expression states that each entry in an auxiliary work-tape segment has at most one symbol. Each assignment that satisfies the expressions in parts (a) and (b) above implies a string of length |x| + 3. The string corresponds to the input tape of M, and consists of input symbols, endmarker

symbols and $, and state symbols. In particular, the symbol X is at location j in the string if and only if wi,0,j,X is assigned the value 1. Similarly, each assignment that satisfies the expressions in parts (c) and (d) above for a specific value r, provides a string of length t + 1 that corresponds to the rth auxiliary work tape of M. The string consists of auxiliary work tape symbols and state symbols. In particular, the string consists of the symbol X at location j if and only if wi,r,j,X is assigned the value 1. The Structure of Einit The expression Einit is the conjunction of the following three Boolean expressions. a. w0,0,1, w0,0,2,q0 { w0,0,j+2,aj | 1 j |x| } w0,0,|x|+3,$.

This expression states that in the initial configuration the input segment consists of the string q0a1 an$, where aj denotes the jth input symbol in x. b. { w0,r,j,q0 | 1 j t + 1 } for 1 r m.

This expression states that in the initial configuration each auxiliary work-tape segment contains the initial state q0. c. w0,r,j,B w0,r,j,q0 { w0,r,s,B | 1 s t+1 and s j } for 1 j t+1 and 1 r m.

This expression states that in the initial configuration each auxiliary work-tape segment consists of blank symbols B and at most one appearance of q0. Each assignment that satisfies Einit corresponds to an initial configuration of M on input x. Moreover, each also satisfies Econf0. The Structure of Erulei and Eaccept The expression Erulei is the conjunction of the following two Boolean expressions. a. b. { wi, | is in } { (wi, 1 wi, 2) |

1,

are in and

}.

The expression in part (a) implies, that for each assignment that satisfies Erulei, at least one of the variables wi, has the value 1. The expression in part (b) implies, that for each assignment that satisfies Erulei, at most one of the variables wi, has a value 1. Hence, each assignment that satisfies Erulei assigns the value 1 to exactly one of the variables wi, , namely, to the variable that corresponds to the transition rule used in the ith move of the computation in question. The expression Eaccept is of the form { wt, | takes M into an accepting state }. The Structure of Efollowi

The expression Efollowi is the conjunction of the following Boolean expressions. a. { (wi,0,j,X wi-1,0,j-1,Y wi-1,0,j,Z wi-1,0,j+1,W wi, ) | X, Y, Z, W, and such that X = f0(Y, Z, W, ) } for 1 j |x| + 3. b. { (wi,r,j,X wi-1,r,j-1,Y wi-1,r,j,Z wi-1,r,j+1,W wi, ) | X, Y, Z, W, and such that X = fr(Y, Z, W, ) } for 1 r m and 1 j t + 1. where fr(Y, Z, W, ) is a function that determines the replacement X for a symbol Z in a configuration, resulting from the application of the transition rule (see Figure 5.3.2).

Figure 5.3.2 The value X of fr(Y, Z, W, ). Z is assumed to be enclosed between Y on its left and W on its right. wi-1,0,0,Y , . . . , wi-1,m,0,Y , wi-1,0,|x|+4,W , wi-1,1,t+2,W , . . . , wi-1,m,t+2,W are new variables. They are introduced to handle the boundary cases in which the symbol Z in fr(Y, Z, W, ) corresponds to an extreme (i.e., leftmost or rightmost) symbol for a tape. If = (q, a, b1, . . . , bm, p, d0, c1, d1, . . . , cm, dm), then the value X of the function fr(Y, Z, W, ) satisfies X = p whenever one of the following cases holds. a. Z = q and dr = 0. b. Y = q and dr = +1. c. W = q and dr = -1. Similarly, X = cr whenever one of the following cases holds, 1 a. Z = q, W = br, and dr = +1. b. Y = q, Z = br, and dr = 0. c. Y = q, Z = br, and dr = -1. On the other hand, a. X = W whenever Z = q, r = 0, and d0 = +1. b. X = Y whenever Z = q and dr = -1. In all the other cases X = Z because the head of the rth tape is "too far" from Z. r m.

The result now follows because TK on input x can compute t = T(|x|) in polynomial time and then output (the string that represents) Ex. Example 5.3.2 Let M be the Turing machine in Figure 5.3.3(a).

Figure 5.3.3

(a) A Turing machine M. (b) The effect that configurations of M.

1,

2,

3,

and

have on the

The time complexity of M is T(n) = n + 2. On input x = ab the Turing machine has an accepting computation C0 C1 C2 C3 C4 of t = 4 moves, where each Ci is a configuration (uqv, u'qv') that satisfies uv = ab$ and |u'v'| t. Using the notation in the proof of Theorem 5.3.1, the following equalities hold for the M and x above. Einit = w0,0,1, w0,0,2,q0 w0,0,3,a w0,0,4,b w0,0,5,$

(w0,1,1,q 0 w0,1,2,q0 w0,1,3,q 0 w0,1,4,q 0 w0,1,5,q0) (w0,1,1,B w0,1,1,q0 w0,1,2,B w0,1,3,B w0,1,4,B w0,1,5,B) (w0,1,2,B w0,1,2,q0 w0,1,1,B w0,1,3,B w0,1,4,B w0,1,5,B) (w0,1,3,B w0,1,3,q0 w0,1,1,B w0,1,2,B w0,1,4,B w0,1,5,B) (w0,1,4,B w0,1,4,q0 w0,1,1,B w0,1,2,B w0,1,3,B w0,1,5,B) (w0,1,5,B w0,1,5,q0 w0,1,1,B w0,1,2,B w0,1,3,B w0,1,4,B)

Erulei = (wi,

wi,
1 1 1 2 2 3

wi,

wi, 4)

(wi, (wi, (wi, (wi, (wi, (wi, Eaccept = w4,

4

wi, 2) wi, 3) wi, 4) wi, 3) wi, 4) wi, 4)

Figure 5.3.3(b) illustrates the changes in the configurations of M due to the transition rules 2, 3, and 4. The 3-Satisfiability Problem

1,

A slight modification to the the previous proof implies the NP-completeness of the following restricted version of the satisfiability problem. Definitions A Boolean expression is said to be a literal if it is a variable or a negation of a variable. A Boolean expression is said to be a clause if it is a disjunction of literals. A Boolean expression is said to be in conjunctive normal form if it is a conjunction of clauses. A Boolean expression is said to be in k-conjunctive normal form if it is in conjunctive normal form and each of its clauses consists of exactly k literals. The k-satisfiability problem asks for any given Boolean expression in k-conjunctive normal form whether the expression is satisfiable. With no loss of generality, in what follows it is assumed that no variable can appear more than once in any given clause. Theorem 5.3.2 The 3-satisfiability problem is NP-complete.

Proof The expression Ex in the proof of Theorem 5.3.1 needs only slight modifications to have a 3-conjunctive normal form.

a.

Except for the expressions Efollowi and part (c) of Einit, all the other expressions can be modified to be in conjunctive normal form by using the equivalence (w1 w2) (w1) (w2). b. Each expression in Efollowi and part (c) of Einit can be modified to be in conjunctive normal form by using the equivalence w1 (w2 w3) (w1 w2) (w1 w3). c. Each disjunction w1 ws with s > 3 clauses can be modified to be in 3-conjunctive normal form by repeatedly replacing subexpressions of the form w1 ws with subexpressions of the form (w1 w2 w) (w w3 ws), where the w's are new variables. The NP-completeness result for the satisfiability problem is of importance in the study of problems for two reasons. First, it exhibits the existence of an NP-complete problem. And, second, it is useful in showing the NP-hardness of some other problems. [next] [prev] [prev-tail] [front] [up]