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

5.3 Nondeterministic Polynomial Time

      From Nondeterministic to Deterministic Time
      The Satisfiability Problem
      The Structure of E_x
      The Variables of E_x
      The Structure of E_{conf_i}
      The Structure of E_init
      The Structure of E_{rule_i} and E_accept
      The Structure of E_{follow_i}
      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 M₁ there exists an equivalent deterministic Turing transducer M₂ with the following characteristics. If M₁ halts on a given input x in t moves, then M₂ on such an input halts within 2^ct moves, where c is some constant that depends only on M₁. Moreover, in such a case M₂ visits at most 2t locations on each of its auxiliary work tapes.

Proof Let M₁ and M₂ be the Turing Transducers M₁ and M₂ of Theorem 4.3.1. Assume that M₁ halts on input x in t steps. Then M₂ needs to consider only the strings in {1, . . . , r}* whose lengths are no greater than t or t + 1, depending on whether M₁ accepts or rejects x, respectively. The number of such strings is no greater than (r + 1)^t+1.

For each string = i₁ i_j in {1, . . . , r}* the Turing transducer M₂ uses some number of moves linear in j to derive and to try simulating a sequence of moves of the form C C. Consequently, M₂ needs some number of moves linear in (r + 1)^t+1t. 2^ct is therefore a bound on the number of moves, because v = 2^{log v} for every positive integer value v.

Similarly, for each string = i₁ i_j the Turing transducer M₂ 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 M₁. By setting the heads of the auxiliary work tapes at their initial positions before starting the simulation of M₁ 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.

The constants 0 (false) and 1 (true) are Boolean expressions.
Each variable x is a Boolean expression.
If E₁ and E₂ are Boolean expressions, then so are the negation ¬E₁, the conjunction E₁ $/\$ E₂, the disjunction E₁ $\/$ E₂, and the parenthesizing (E₁).

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 E₁ and E₂ are Boolean expressions, then E₁ $\/$ E₂ has the value 1 whenever E₁ or E₂ has the value 1. E₁ $\/$ E₂ has the value 0 whenever both E₁ and E₂ have the value 0. The value of E₁ $/\$ E₂ is 1 if both E₁ and E₂ have the value 1, otherwise E₁ $/\$ E₂ 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 L_sat = { E | E is a satisfiable Boolean expression }.

Example 5.3.1 The Boolean expression E = x₂ $/\$ x₃ $\/$ (¬x₁ $/\$ x₂) is satisfiable by each assignment in which x₂ = 1 and x₃ = 1, as well as by each assignment in which x₁ = 0 and x₂ = 1. All the other assignments provide a 0 value to E. (x₂ $/\$ x₃) $\/$ ((¬x₁) $/\$ x₂) 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 T_K, such that T_K reduces K to the satisfiability problem. For the purpose of the proof consider any problem K in NP. Assume that M = <Q, , , , q₀, B, F> is a nondeterministic Turing machine with Q $/~\$ ( {¢, $}) = Ø that decides K in T(n) = O(n^k) time. Let m denote the number of auxiliary work tapes of M; then T_K can be a Turing transducer that on input x outputs a Boolean expression E_x of the following form.

The Structure of E_x

The Boolean expression E_x describes how an accepting computation of M on input x should look. E_x is satisfiable by a given assignment if and only if the assignment corresponds to an accepting computation C₀ C₁ C_T(|x|) of M on input x. The expression has the following structure, where t = T(|x|).

E_conf₀ $/\$ $/\$ E_{conf_t} states that an accepting computation consists of a sequence C₀, . . . , C_t of t + 1 configurations. E_init states that C₀ is an initial configuration.

E_rule₁ $/\$ $/\$ E_{rule_t} states that an accepting computation uses a sequence of t transition rules. E_accept 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.

E_{follow_i} states that M by using the ith transition rule in reaches configuration C_i from configuration C_i-1, 1 i t.

The Variables of E_x

The Boolean expression E_x uses variables of the form w_i,r,j,X and variables of the form w_i,. Each variable provides a statement about a possible property of an accepting computation. An assignment that satisfies E_x 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.

w_i,r,j,X states that X is the jth character of the rth tape in the ith configuration, 0 r m. r = 0 refers to the input tape, and 1 r m refers to the rth auxiliary work tape.

w_i, states that is the transition rule in the ith move of the computation.

The Structure of E_{conf_i}

The expression E_{conf_i} is the conjunction of the following Boolean expressions.

$\/$ { w_i,0,j,X | X is in {¢, $} Q } for 1 j |x| + 3.
This expression states that a configuration has an input segment with |x| + 3 entries, with each entry having at least one symbol from {¢, $} Q.
$/\$ { ¬(w_i,0,j,X $/\$ w_i,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.
$\/$ { w_i,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.
$/\$ { ¬(w_i,r,j,X $/\$ w_i,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 w_i,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 w_i,r,j,X is assigned the value 1.

The Structure of E_init

The expression E_init is the conjunction of the following three Boolean expressions.

w_0,0,1, $/\$ w_0,0,2,q₀ $/\$ { w_{0,0,j+2,a_j} | 1 j |x| } $/\$ w_0,0,|x|+3,$.
This expression states that in the initial configuration the input segment consists of the string ¢q₀a₁ a_n$, where a_j denotes the jth input symbol in x.
$\/$ { w_0,r,j,q₀ | 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 q₀.
w_0,r,j,B $\/$ w_0,r,j,q₀ $/\$ { w_0,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 q₀.

Each assignment that satisfies E_init corresponds to an initial configuration of M on input x. Moreover, each also satisfies E_conf₀.

The Structure of E_{rule_i} and E_accept

The expression E_{rule_i} is the conjunction of the following two Boolean expressions.

$\/$ { w_i, | is in }
$/\$ { ¬(w_i,₁ $/\$ w_i,₂) | ₁, ₂ are in and ₁ ₂ }.

The expression in part (a) implies, that for each assignment that satisfies E_{rule_i}, at least one of the variables w_i, has the value 1. The expression in part (b) implies, that for each assignment that satisfies E_{rule_i}, at most one of the variables w_i, has a value 1. Hence, each assignment that satisfies E_{rule_i} assigns the value 1 to exactly one of the variables w_i,, namely, to the variable that corresponds to the transition rule

used in the ith move of the computation in question.

The expression E_accept is of the form $\/$ { w_t, | takes M into an accepting state }.

The Structure of E_{follow_i}

The expression E_{follow_i} is the conjunction of the following Boolean expressions.

$\/$ { (w_i,0,j,X $/\$ w_i-1,0,j-1,Y $/\$ w_i-1,0,j,Z $/\$ w_i-1,0,j+1,W $/\$ w_i,) | X, Y, Z, W, and such that X = f₀(Y, Z, W, ) } for 1 j |x| + 3.
$\/$ { (w_i,r,j,X $/\$ w_i-1,r,j-1,Y $/\$ w_i-1,r,j,Z $/\$ w_i-1,r,j+1,W $/\$ w_i,) | X, Y, Z, W, and such that X = f_r(Y, Z, W, ) } for 1 r m and 1 j t + 1.

where

f_r(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 f_r(Y, Z, W,

Z is assumed to be enclosed between Y on its left and W on its right.

w_i-1,0,0,Y, . . . , w_i-1,m,0,Y, w_{i-1,0,|x|+4,W}, w_i-1,1,t+2,W, . . . , w_i-1,m,t+2,W

are new variables. They are introduced to handle the boundary cases in which the symbol Z in f_r(Y, Z, W,

) corresponds to an extreme (i.e., leftmost or rightmost) symbol for a tape.

= (q, a, b₁, . . . , b_m, p, d₀, c₁, d₁, . . . , c_m, d_m), then the value X of the function f_r(Y, Z, W,

) satisfies X = p whenever one of the following cases holds.

Z = q and d_r = 0.
Y = q and d_r = +1.
W = q and d_r = -1.

Similarly, X = c_r whenever one of the following cases holds, 1

Z = q, W = b_r, and d_r = +1.
Y = q, Z = b_r, and d_r = 0.
Y = q, Z = b_r, and d_r = -1.

On the other hand,

X = W whenever Z = q, r = 0, and d₀ = +1.
X = Y whenever Z = q and d_r = -1.

In all the other cases X = Z because the head of the rth tape is "too far" from Z.

The result now follows because T_K on input x can compute t = T(|x|) in polynomial time and then output (the string that represents) E_x.

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

₁,

₂,

₃, and

₄ have on the configurations of M.

The time complexity of M is T(n) = n + 2. On input x = ab the Turing machine has an accepting computation C₀

C₁

C₂

C₃

C₄ of t = 4 moves, where each C_i is a configuration (uqv, u'qv') that satisfies uv = ¢ab$ and |u'v'|

Using the notation in the proof of Theorem 5.3.1, the following equalities hold for the M and x above.

E_init	=	w_0,0,1, $/\$ w_0,0,2,q₀ $/\$ w_0,0,3,a $/\$ w_0,0,4,b $/\$ w_0,0,5,$

		$/\$ (w_{0,1,1,_q₀} $\/$ w_0,1,2,q₀ $\/$ w_{0,1,3,_q₀} $\/$ w_{0,1,4,_q₀} $\/$ w_0,1,5,q₀)

		$/\$ (w_0,1,1,B $\/$ w_0,1,1,q₀ $/\$ w_0,1,2,B $/\$ w_0,1,3,B $/\$ w_0,1,4,B $/\$ w_0,1,5,B)

		$/\$ (w_0,1,2,B $\/$ w_0,1,2,q₀ $/\$ w_0,1,1,B $/\$ w_0,1,3,B $/\$ w_0,1,4,B $/\$ w_0,1,5,B)

		$/\$ (w_0,1,3,B $\/$ w_0,1,3,q₀ $/\$ w_0,1,1,B $/\$ w_0,1,2,B $/\$ w_0,1,4,B $/\$ w_0,1,5,B)

		$/\$ (w_0,1,4,B $\/$ w_0,1,4,q₀ $/\$ w_0,1,1,B $/\$ w_0,1,2,B $/\$ w_0,1,3,B $/\$ w_0,1,5,B)

		$/\$ (w_0,1,5,B $\/$ w_0,1,5,q₀ $/\$ w_0,1,1,B $/\$ w_0,1,2,B $/\$ w_0,1,3,B $/\$ w_0,1,4,B)



E_{rule_i}	=	(w_i,₁ $\/$ w_i,₂ $\/$ w_i,₃ $\/$ w_i,₄)

		$/\$ ¬(w_i,₁ $/\$ w_i,₂)

		$/\$ ¬(w_i,₁ $/\$ w_i,₃)

		$/\$ ¬(w_i,₁ $/\$ w_i,₄)

		$/\$ ¬(w_i,₂ $/\$ w_i,₃)

		$/\$ ¬(w_i,₂ $/\$ w_i,₄)

		$/\$ ¬(w_i,₃ $/\$ w_i,₄)



E_accept	=	w_4,₄

Figure 5.3.3(b) illustrates the changes in the configurations of M due to the transition rules ₁, ₂, ₃, and ₄.

The 3-Satisfiability Problem

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 E_x in the proof of Theorem 5.3.1 needs only slight modifications to have a 3-conjunctive normal form.

Except for the expressions E_{follow_i} and part (c) of E_init, all the other expressions can be modified to be in conjunctive normal form by using the equivalence ¬(w₁ $/\$ w₂) (¬w₁) $\/$ (¬w₂).
Each expression in E_{follow_i} and part (c) of E_init can be modified to be in conjunctive normal form by using the equivalence w₁ $\/$ (w₂ $/\$ w₃) (w₁ $\/$ w₂) $/\$ (w₁ $\/$ w₃).
Each disjunction w₁ $\/$ $\/$ w_s with s > 3 clauses can be modified to be in 3-conjunctive normal form by repeatedly replacing subexpressions of the form w₁ $\/$ $\/$ w_s with subexpressions of the form (w₁ $\/$ w₂ $\/$ w) $/\$ (¬w $\/$ w₃ $\/$ $\/$ w_s), 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]