5.2  A Time Hierarchy

      Lower Bounds on Time Complexity
      Tractability and Intractability

Intuitively, it seems obvious that some problems require more time to solve than others. The following result confirms this intuitive assessment while implying the existence of a time hierarchy for the class of language recognition problems.

Definitions     A function T(n) is said to be time-constructible if there exists a T(n) time-bounded, deterministic Turing machine that for each n has an input of length n on which it makes exactly T(n) moves. The function is said to be fully time-constructible if there exists a deterministic Turing machine that makes exactly T(n) moves on each input of length n. A function S(n) is said to be space-constructible if there exists an S(n) space-bounded, deterministic Turing machine that for each n has an input of length n on which it requires exactly S(n) space. The function is said to be fully space-constructible if there exists a deterministic Turing machine that requires exactly S(n) space on each input of length n.

Example 5.2.1    The deterministic Turing machine M in Figure 5.2.1

Figure 5.2.1 A T(n) = 2n time-bounded, deterministic Turing machine.

The existence of M implies that T(n) = 2n is a time-constructible function, because

1.  M is 2n time-bounded, and
2.  For each n there exists the input 1ⁿ of length n on which M makes exactly 2n moves.

Convention     In this section M_x denotes a Turing machine that is represented by the string x of the following form. If x = 1^jx₀ for some j 0 and for some standard binary representation x₀ of a deterministic Turing machine M, then M_x denotes M. Otherwise, M_x denotes a deterministic Turing machine that accepts no input. The string x is said to be a padded binary representation of M_x.

Theorem 5.2.1    Consider any function T₁(n) and any fully time-constructible function T₂(n), that for each c > 0 have an n_c such that T₂(n) c(T₁(n))² for all n n_c. Then there is a language which is in DTIME (T₂(n)) but not in DTIME (T₁(n)).

Proof     Let T₁(n) and T₂(n) be as in the statement of the theorem. Let U be a universal Turing machine similar to the universal Turing transducer in the proof of Lemma 5.1.1. The main difference is that here U assumes an input (M, x) in which M is represented by a padded binary representation instead of a standard binary representation. U starts each computation by going over the "padding" 1^j until it reaches the first 0 in the input. Then U continues with its computation in the usual manner while ignoring the padding. U uses a third auxiliary work tape for keeping track of the distance of its input head from the end of the padding. The result is shown by diagonalization over the language L = { v | v is in {0, 1}*, and U does not accept (M_v, v) in T₂(|v|) time }.

L is obtained from the diagonal of the table T_universal (see Figure 5.2.2).

Figure 5.2.2 Hypothetical table Tuniversal indicating membership in the language { (Mw, u) | U accepts (Mw, u) in T2(|u|) time }.

Specifically, for the purpose of showing that L is not in DTIME (T₁(n)), assume to the contrary that L is in the class. Under this assumption, there is a dT₁(n) time-bounded, deterministic Turing machine M that accepts L, for some constant d. Let x₀ be a standard binary representation of M, and c be the corresponding constant c_M implied by Lemma 5.1.1 for the representation x₀ of M. Let x = 1^jx₀ for some j that satisfies j + c(dT₁(j + |x₀|))² T₂(j + |x₀|), that is, x = 1^jx₀ for a large enough j to allow U sufficient time T₂(|x|) for simulating the whole computation of M_x on input x. Such a value j exists because for big enough j the following inequalities hold.

j + c 2		(j + |x 0|) + c 2
		T1(j + |x0|) + c 2
		(1 + cd2) 2
		T2(j + |x0|)

Consider the string x = 1^jx₀. By definition, |x| = j + |x₀| and so j + c(dT₁(|x|))² T₂(|x|). Moreover, x is a padded binary representation of M. For the string x one of the following two cases must hold. However, neither of them can hold, so implying the desired contradiction to the assumption that L is in DTIME (T₁(n)).

Case 1

x is in L. The assumption together with L = L(M_x) imply that M_x accepts x in dT₁(|x|) time. In such a case, by Lemma 5.1.1 U accepts (M_x, x) in j + c(dT₁(|x|))² T₂(|x|) time. On the other hand, x in L together with the definition of L imply that U does not accept x in T₂(|x|) time. The contradiction implies that this case cannot hold.

Case 2

x is not in L. The assumption together with L = L(M_x) imply that M_x does not accept x. In such a case, U does not accept (M_x, x) either. On the other hand, x not in L together with the definition of L imply that U accepts (M_x, x). The contradiction implies that this case cannot hold either.

Step 1

M stores (M_x, x) in its first auxiliary work tape. That is, M stores the string x, followed by the separator 01, followed by the representation 011 of the left endmarker ¢, followed by x, followed by the representation 0111 of the right endmarker $. In addition, M encloses the sequence of strings above between the "left endmarker" and the "right endmarker" , respectively.

Step 2

M computes the value of T₂(|x|) and stores it in the second auxiliary work tape.

Step 3

M follows the moves of U on the content of its first auxiliary work tape, that is, on (M_x, x). M uses its third and fourth auxiliary work tapes for recording the content of the two auxiliary work tapes of U. During the simulation M interprets as the left endmarker ¢, and as the right endmarker $. M halts in an accepting configuration if it determines that U does not reach an accepting state in T₂(|x|) moves. Otherwise, M halts in a nonaccepting configuration.

Example 5.2.2    Let T₁(n) = n^k and T₂(n) = 2ⁿ. T₁(n) and T₂(n) satisfy the conditions of Theorem 5.2.1. Therefore the class DTIME (2ⁿ) properly contains the class DTIME (n^k).

 Lower Bounds on Time Complexity

In addition to implying the existence of a time hierarchy for the language recognition problems, Theorem 5.2.1 can be used to show lower bounds on the time complexity of some problems. Specifically, consider any two functions T₁(n) and T₂(n) that satisfy the conditions of Theorem 5.2.1. Assume that each membership problem K_i for a language in DTIME (T₂(n)) can be reduced by a T₃(n) time-bounded, deterministic Turing transducer M_i to some fixed problem K (see Figure 5.2.3).

Figure 5.2.3 A set of Turing transducers M1, M2, . . . for reducing the problems K1, K2, . . . in DTIME (T2(n)) to a given language recognition problem K. Each Mi on instance x of Ki provides an instance y of K, where K has the answer yes for y if and only if Ki has the answer yes for x.

Example 5.2.3    Consider the time bounds T₁(n) = 2^an, T₂(n) = 2^bn for b > 2a, and T₃(n) = f(n) = n log n. For such a choice, T₃(n) + T(f(n)) > cT₁(n) implies that n log n + T(n log n) > c2^an. By substituting m for n log n it follows that T(m) > c2^an - m = c2^{am/log n} - m c2^{am/log m} - m 2^{dm/log m} or, equivalently, that T(n) > 2^{dn/log n} for some constant d.

The approach above for deriving lower bounds is of special interest in the identification of intractable problems, that is, problems that require impractical amounts of resources to solve. Such an identification can save considerable effort that might otherwise be wasted in trying to solve intractable problems.

 Tractability and Intractability

In general, a problem is considered to be tractable if it is of polynomial time complexity. This is because its time requirements grow slowly with input length. Conversely, problems of exponential time complexity are considered to be intractable, because their time requirements grow rapidly with input length and so can be practically solved only for small inputs. For instance, an increase by a factor of 2 in n, increases the value of a polynomial p(n) of degree k by at most a factor of 2^k. On the other hand, such an increase at least squares the value of 2^p(n).

The application of the approach above in the identification of intractable problems employs polynomially time-bounded reductions.

A problem K₁ is said to be polynomially time reducible to a problem K₂ if there exist polynomially time-bounded, deterministic Turing transducers T_f and T_g that for each instance I₁ of K₁ satisfy the following conditions (see Figure 5.2.4).

Figure 5.2.4 Reduction by polynomially time-bounded, deterministic Turing transducers Tf and Tg.

1.  T_f on input I₁ gives an instance I₂ of K₂.
2.  K₁ has a solution S₁ at I₁ if and only if K₂ has a solution S₂ at I₂, where S₁ is the output of T_g on input S₂.

A given complexity class C of problems can be used to show the intractability of a problem K by showing that the following two conditions hold.

1.  C contains some intractable problems.
2.  Each problem in C is polynomially time reducible to K, that is, K is at least as hard to solve as any problem in C.

The observation above sparks our interest in the "easiest" intractable problems K, and in the complexity classes C whose intractable problems are all "easiest" intractable problems.

In what follows, a problem K is said to be a C-hard problem with respect to polynomial time reductions, or just a C-hard problem when the polynomial time reductions are understood, if every problem in the class C is polynomially time reducible to the problem K. The problem K is said to be C-complete if it is a C-hard problem in C.

Our interest here is in the cases that C = NP and C = PSPACE.

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