5.5  Polynomial Space

      From Nondeterministic Space to Deterministic Time
      From Nondeterministic to Deterministic Space
      PSPACE-Complete Problems
      Closure Properties

By Corollary 5.3.1 NTIME (T(n)) DSPACE (T(n)) and so PSPACE contains NP. Moreover, by Theorem 5.5.1 PSPACE is contained in EXPTIME . These containments suggest that PSPACE be studied similarly to NP. Specifically, such a study will be important in the remote possibility that NP turns out to be equal to P -- the same reason the study was important for NP in the first place. However, if NP turns out to be different from P, then the study of PSPACE might provide some insight into the factors that increase the complexity of problems.

Lemma 5.5.1    An S(n) log n space-bounded Turing machine M can reach at most 2^dS(n) configurations on a given input of length n. d is assumed to be some constant dependent only on M.

Proof     Consider any Turing machine M = <Q, , , , q₀, B, F> of space complexity S(n) log n. For input x of length n the Turing machine M can have at most |Q| (n + 2) (S(n)||^S(n))^m different configurations. |Q| denotes the number of states of M, m denotes the number of auxiliary work tapes of M, and || denotes the size of the auxiliary work-tape alphabet of M.

The factor of |Q| arises because in the configurations (uqv, u₁qv₁, . . . , u_mqv_m) which satisfy uv = ¢x$ the state q comes from a set Q of cardinality |Q|. The factor n + 2 arises because the input head position |u| can be in n + 2 locations. S(n) represents the number of possible locations for the head of an auxiliary work tape, and ||^S(n) represents the number of different strings that can be stored on an auxiliary work tape.

The expression |Q| (n + 2) (S(n)||^S(n))^m has a constant d such that

|Q| (n + 2) (S(n)||S(n))m	=	2log |Q|2log (n+2)(2log S(n)2S(n)log ||)m
		2dS(n)

 From Nondeterministic Space to Deterministic Time

By Corollary 5.3.1 nondeterministic and deterministic time satisfy the relation NTIME (T(n)) _c>0DTIME (2^cT(n)). The following theorem provides a refinement to this result because NTIME (T(n)) NSPACE (T(n)).

Definition     The configurations tree of a Turing machine M on input x is a possibly infinite tree defined in the following manner. The root of is a node labeled by the initial configuration of M on input x. A node in , which is labeled by a configuration C₁, has an immediate successor that is labeled by configuration C₂ if and only if C₁ C₂.

Theorem 5.5.1    If S(n) log n then

Proof     Consider any S(n) space-bounded Turing machine M₁ = <Q, , , , q₀, B, F>. A deterministic Turing machine M₂ can determine if M₁ accepts a given input x by determining whether the configurations tree , of M₁ on input x, contains an accepting configuration. M₂ can do so by finding the set A of all the configurations in , and then checking whether the set contains an accepting configuration. The set A can be generated by following the algorithm.

Step 1

Initiate A to contain only the initial configuration of M₁ on input x.

Step 2

For each configuration C in A that has not been considered yet determine all the configurations that M₁ can reach from C in a single move, and insert them to A.

Step 3

Repeat Step 2 as long as more configurations can be added to A.

Example 5.5.1    Let M₁ be the Turing machine in Figure 5.5.1(a).

Figure 5.5.1 (a) A Turing machine M1. (b) The configurations tree of M1 on input aa.

i₁ i_t

i₁ i_t

The algorithm in the proof of Theorem 5.5.1 inserts C to A in Step 1. The first iteration of Step 2 determines the immediate successors C₁ and C₃ of C, and inserts them into A. The second iteration considers either the configuration C₁ or the configuration C₃.

If C₁ is considered before C₃, then C₁₁ and C₁₃ are the configurations contributed by C₁ to A. In such a case, C₃ contributes C₃₃ to A.

Upon completion A contains the configurations C, C₁, C₃, C_{1 1}, C_{1 3} (= C_{3 1}), C_{3 3}, C_{1 1 5}, C_{1 3 5} (= C_{3 1 5}), C_{3 3 5}, . . . , C_{3 1 5 6 10 12 14 13 21}.

 From Nondeterministic to Deterministic Space

The previous theorem, together with Corollary 5.3.1, imply the hierarchy DLOG NLOG P NP PSPACE EXPTIME (see Figure 5.5.2).

Figure 5.5.2 A refinement to the classification in Figure 5.3.1.

The following theorem provides an approach more economical in space, than that of the proof of the previous theorem. However, the improvement in the space requirements is achieved at the cost of slower simulations.

Theorem 5.5.2    If S(n) is a fully space-constructible function and S(n) log n then

Proof     Consider any cS(n) space-bounded Turing machine M₁, where S(n) log n is fully space-constructible. With no loss of generality it can be assumed that on entering into an accepting configuration the auxiliary work tapes of M₁ are all blank, and the input head of M₁ is on the right endmarker $. In addition, it can be assumed that M₁ has exactly one accepting state q_f. Consequently, an accepting computation of M₁ on a given input x must end at the accepting configuration (¢xq_f$, q_f, . . . , q_f).

By definition, M₁ accepts a given input x if and only if M₁ on input x has a sequence of moves, starting at the initial configuration C₀ of M₁ on input x and ending at the accepting configuration C_f of M₁ on input x. By Lemma 5.5.1 the Turing machine M₁ can reach at most 2^dS(n) different configurations on an input of length n. By Theorem 5.5.1 each configuration requires at most d's(n) space when the input string is excluded. Consequently, M₁ accepts x if and only if it has a sequence of at most 2^dS(|x|) moves that starts at C₀ and ends at C_f.

A deterministic Turing machine M₂ can determine whether M₁ accepts an input x by the algorithm in Figure 5.5.3.

C0 := the initial configuration of M1 on input x
Cf := the accepting configuration of M1 on input x
if R(C0, Cf, 2dS(|x|)) then accept
reject
function R(C1, C2, t)
   if t  1 then
        if M1 can in t steps reach configuration C2
               from configuration C1 then return (true)
    else for each configuration C of M1 on input x
               of length  d's(|x|) do
        if R(C1, C, t/2) and
            R(C, C2, t/2) then return (true)
    return (false)
end                                                                              

The algorithm uses a recursive function R(C₁, C₂, t) whose task is to determine whether M₁ on input x has a sequence of at most t moves, starting at C₁ and ending at C₂. The property is checked directly when t 1. Otherwise, it is checked recursively by exhaustively searching for a configuration C of M₁, such that both R(C₁, C, t/2) and R(C, C₂, t/2) hold.

The algorithm uses O(S(n)) levels of recursion in R(C₁, C₂, t). Each level of recursion requires space O(S(n)). Consequently M₂ uses O( (S(n))²) space.

When it derives the configurations of M₁, M₂ relies on the property that S(n) is space-constructible.

 PSPACE-Complete Problems

Approaches similar to those used for showing the NP-hardness of some given problems, can also be used for showing PSPACE-hardness. The following theorem is an example of a PSPACE-complete problem whose PSPACE-hardness is shown by a generic transformation.

Theorem 5.5.3    The membership problem for linear bounded automata or, equivalently, for L = { (M, x) | M is a linear bounded automaton that accepts x } is a PSPACE-complete problem.

Proof     The language L is accepted by a nondeterministic Turing machine M_U similar to the universal Turing machine in the proof of Theorem 4.4.1. M_U on input (M, x) nondeterministically finds a sequence of moves of M on x. M_U accepts the input if and only if the sequence of moves starts at the initial configuration of M on input x, and ends at an accepting configuration. The computation of M_U proceeds in the following manner.

M_U starts by constructing the initial configuration C₀ of M on input x. Then it repeatedly and nondeterministically finds a configuration C that M can reach in one step from the last configuration that has been determined for M by M_U . M_U accepts (M, x) if and when it reaches an accepting configuration of M.

By construction, M_U requires a space no greater than the amount of memory required for recording a single configuration of M. A single configuration (uqv, u₁qv₁, . . . , u_mqv_m) of M requires space equal to the amount of memory needed for recording a single symbol times the number of symbols in the configuration, that is,

O(|M|( (1 + |uv|) + (1 + |u1v1|) + + (1 + |umvm|) ))	=
O(|M|(m + 1)(1 + |x|))	=	O(|M|2|x|)

To show that the membership problem for L is PSPACE-hard, consider any problem K in PSPACE. Assume that A is a deterministic Turing machine of space complexity S(n) = O(n^k) that decides K. From (A, S(n)) a polynomially time-bounded, deterministic Turing transducer T_K can be constructed to output the pair (M, y) on input x.

y is assumed to be the string #^jx, where j = S(|x|) and # is a new symbol. M is assumed to be a linear bounded automaton, which on input #^jx simulates the computation of A on x with j space. That is, M accepts y if and only if A accepts x within j space.

Example 5.5.2    Let A be the Turing machine in Figure 5.3.3. Using the terminology in the proof of Theorem 5.5.3, the corresponding linear bounded automaton M can be the one given in Figure 5.5.4.

Figure 5.5.4 A linear bounded automaton corresponding to the Turing machine of Figure 5.3.3.

M starts each computation by copying the leading symbols #, from the input to its auxiliary work tape. Then M nondeterministically locates its auxiliary work-tape head over one of the symbols #. Finally, M follows a computation similar to A's on the remainder of the input. The main difference is that M expects the symbol # whenever A scans the left endmarker ¢ or a blank symbol B.

The following theorem is an example of a problem whose PSPACE-hardness is shown by reduction from another PSPACE-hard problem.

Theorem 5.5.4    The inequivalence problem for finite-state automata is PSPACE-complete.

Proof     Let (M₁, M₂) be any given pair of finite-state automata. A Turing machine M can determine the inequivalency of M₁ and M₂ by finding nondeterministically an input a₁ a_N that is accepted by exactly one of the finite-state automata M₁ and M₂.

M starts its computation by determining the set S₀ of all the states that M₁ and M₂ can reach on empty input. With no loss of generality it is assumed that M₁ and M₂ have disjoint sets of states. Then M determines, one at a time, the symbols in a₁ a_N . For each symbol a_i that M determines, M also finds the set S_i (from those states that are in S_i-1) that M₁ and M₂ can reach by consuming a_i.

M halts in an accepting configuration upon, and only upon, finding an S_N that satisfies either of the following conditions.

1.  S_N contains an accepting state of M₁ and no accepting state of M₂.
2.  S_N contains an accepting state of M₂ and no accepting state of M₁.

To show that the inequivalence problem for finite-state automata is a PSPACE-hard problem, it is sufficient to demonstrate the existence of a polynomially time-bounded, deterministic Turing transducer T that has the following property: T on input (M, x), of a linear bounded automaton M and of an input x for M, outputs a pair (M₁, M₂) of finite-state automata M₁ and M₂. Moreover, M₁ and M₂ are inequivalent if and only if M accepts x.

M₁ can be a finite-state automaton that accepts a given input if and only if the input is not of the form #C₀#C₁# #C_f#. C₀ is assumed to be the initial configuration of M on input x. C_f is assumed to be an accepting configuration of M on input x. C_i is assumed to be a configuration that M can reach in one move from C_i-1, i = 1, . . . , f. The length of each C_i is assumed to equal (n + 3) + m(S(n) + 1), m is assumed to be the number of auxiliary work tapes of M, S(n) is assumed to be the space complexity of M, and # is assumed to be a new symbol.

M₁ can determine that an input is not of such a form, by nondeterministically choosing to check for one of the following conditions.

1.  The first symbol in the input is not #.
2.  The last symbol in the input is not #.
3.  C₀ is not an initial configuration of M on input x.
4.  C_f does not contain an accepting state of M.
5.  C_i is not consistent with C_i-1 for some i (chosen nondeterministically). M₁ can check for this condition by nondeterministically finding a j such that the jth symbol in C_i is not consistent with the jth symbol in C_i-1 and its two neighbors.

By construction, M₁ accepts all inputs if and only if M does not accept x. The result then follows immediately if M₂ is taken to accept all the strings over the input alphabet of M₁.

Example 5.5.3    The Turing machine M in Figure 5.5.1(a) has space complexity of S(n) = n + 2. For the string x = aa the Turing machine M in the proof of Theorem 5.5.4 has the corresponding finite-state automaton M₁ of Figure 5.5.5.

Figure 5.5.5 A finite-state automaton that accepts all inputs if and only if the Turing machine in Figure 5.5.1(a) does not accept aa.

On a given input M₁ nondeterministically chooses to execute one of the subcomponents A₁, A₂, A₃, A₄, or A₅.

A₁ checks that the input does not start with the symbol #. A₂ checks that the input does not end with the symbol #. A₃ checks that the string between the first two # symbols is not the initial configuration of M on input aa. A₄ checks that the accepting state q₄ does not appear in the last configuration C_f.

A₅ checks for inconsistency between consecutive configurations. Its specification is omitted here.

 Closure Properties

The classes NTIME (T(n)) and NSPACE (S(n)) are closed under union and intersection (see Exercise 5.1.3(a)), but it is not known whether they are closed under complementation. However, the following theorem holds for NSPACE (S(n)).

Theorem 5.5.5    The class NSPACE (S(n)) is closed under complementation for S(n) log n.

Proof     Consider any S(n) space-bounded, nondeterministic Turing machine M₁. From M₁ an S(n) space-bounded, nondeterministic Turing machine M₂ can be constructed to accept the complementation of L(M₁).

Specifically, on a given input x the Turing machine M₂ determines whether the configurations tree of M₁ on x contains an accepting configuration. If so, then M₂ rejects x. Otherwise, M₂ accepts x.

M₂ traverses by stages, according to the algorithm in Figure 5.5.6(a).

i := 0 l := length of the initial configuration C0 of M1 on input x N := 1 repeat for each configuration C in i do if C is an accepting configuration then reject l := max(l, length of longest configuration in i+1) N := number of configurations in i+1 i := i + 1 until i > (the number of configurations, of M1 on input x, of length l) accept (a) count := 0 for each configuration C, of M1 on input x, of length l at most  do if C0 * C in exactly i moves then begin count := count + 1 end if count N then reject (b) nextN := 0 for each configuration C', of M1 on input x, of length l do begin countup := false for each configuration C in i do if C C' then countup := true if countup then nextN := nextN + 1 end N := nextN (c)   Figure 5.5.6 (a) A breadth-first search algorithm for accepting the complementation of L(M1). (b) Simulation of "for each configuration C in i do ". (c) Evaluation of the number of configurations in i+1.

M₂ halts during the ith stage in a nonaccepting configuration if it determines an accepting configuration in _i. However, it halts at the end of the ith stage in an accepting configuration if it determines that _i cannot contain new configurations (i.e., by determining that i is greater than the number of configurations M₁ can reach on input x).

The configurations C that are in _i are found nondeterministically from i and the number N of configurations in _i. In particular, M₂ simulates the instructions of the form "for each configuration C in _i do " in accordance with the algorithm in Figure 5.5.6(b). The nondeterminism is required for simulating the sequences of moves C₀ * C.

M₂ determines the number N of configurations in _i+1 by determining which configuration can be directly reached from those that are in _i. The algorithm is given in Figure 5.5.6(c).

The result now follows because by Lemma 5.5.1, the Turing machine M₁ can reach at most 2^O(S(n)) different configurations on inputs of length n, that is, M₂ considers only i 2^O(S(n)) levels of .

The class DTIME (T(n)) is closed under union , intersection, and complementation (see Exercise 5.1.3(b)). The closure of DSPACE (S(n)) under union, intersection, and complementation can be easily shown by direct simulations. For the last operation, however, the following theorem is required.

Definitions     An s space-bounded configuration is a configuration that requires at most s space in each auxiliary work tape. An s space-bounded, backward-moving-configurations tree of a Turing machine M is a tree , defined in the following manner. The root of is labeled by an s space-bounded configuration of M. A node in , labeled by a configuration C₂, has an immediate successor labeled by configuration C₁ if and only if C₁ is an s space-bounded configuration of M such that C₁ C₂.

Theorem 5.5.6    Each S(n) space-bounded, deterministic Turing machine M₁ has an equivalent S(n) space-bounded, deterministic Turing machine M₂ that halts on all inputs.

Proof     Consider any S(n) space-bounded, deterministic Turing machine M₁ = <Q, , , , q₀, B, F>. M₂ can be of the following form. M₂ on a given input x determines the space s_x that M₁ uses on input x. Then M₂ checks whether M₁ has an accepting computation on input x. If so, then M₂ halts in an accepting configuration. Otherwise M₂ halts in a rejecting one.

To determine the value of s_x the Turing machine M₂ initializes s_x to equal 1. Then M₂ increases s_x by 1 as long as it finds an s_x space-bounded configuration C₁, and an (s_x + 1) space-bounded configuration C₂, such that the following conditions hold.

1.  C₁ C₂.
2.  M₁ has an s_x space-bounded, backward-moving-configurations tree , the root of which is C₁ and which contains the initial configuration of M₁ on x.

To check whether M₁ has an accepting computation on input x the Turing machine M₂ searches for an s_x space-bounded, backward-moving-configurations tree that satisfies the following conditions.

1.  The root of is an accepting configuration of M₁ on input x.
2.   contains the initial configuration of M₁ on input x.

C := Croot do if C is an initial configuration then begin while C has a predecessor in s do C := predecessor of C in s return (true) end if C is not a terminal node in s then C := the leftmost successor of C in s else if C has a right neighbor in s then C := the right neighbor C in s else if C has a predecessor in s then C := the predecessor of C in s else return (false) until false   Figure 5.5.7 Depth-first search for an initial configuration in s.

The algorithm is used only on configurations C_root, such that if C_root C' then C' is not an s space-bounded configuration. This property is used by the algorithm to determine the root of _s upon backtracking.

The algorithm relies on the observation that the determinism of M₁ implies the following properties for each s space-bounded, backward-moving-configurations tree _s.

1.  The tree _s is finite because no configuration can be repeated in a path that starts at the root.
2.  The predecessors, successors, and siblings of each node can be determined simply from the configuration assigned to the node.

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