Problem Solving in Automata, Languages, and Complexity

6.2 Time and Space Complexity 287 Proof. If we examine carefully the simulation of multi-tape DTM M by two- way, one-tape DTM A& ...

288 COMPUTATIONAL COMPLl3XsITY the tape cells in the work tape that are visited by the tape head for the space bound of such a D ...

6.2 Time and Space Complexity 289 input tape input tape 0 b a b a a 0 BbabaaB 4 work tape work tape bBaacabB *g\\*.. :b. bBaa ca ...

290 COMPUTATIONAL COMPLEXITY tape in the simulation, if the initial internal position of the work tape head of AP is at the midd ...

6.2 Time and Space Complexity 291 011001 Ltll^4 Figure 6.3: A local configuration. moves left to cell g, then moves left to read ...

292 COMPUTATIONAL COMPLEXITY ~~ bee-dance ‘2 ‘~ bee-dance 111000 r (p,xxooxx ;O) Figure 6.4: The ten moves. Because limn+W t(n)/ ...

6.2 Time and Space Complexity 293 By Theorem 6.10, DTIME(tl(n)) & DTIME(c. tz(n)) = DTIME(tz(n)). Symmetrically, we have DTI ...

294 COMPUTATIONAL COMPLEXITY From the Extended Church-Turing Thesis, we see that these complexity classes are model-independent. ...

6.2 Time and Space Complexity 295 (a) x E A; or (b) There exists a partition II: = ~1~2, where $1 and x2 are nonempty, such that ...

296 COMPUTATIONAL COMPLEXITY simulation move, it writes down the current configuration of M on the third work tape. It compares ...

6.3 Hierarchy Theorems 297 (b) Let ASCB = {x E l(O+ l) +0 1 n(z) = n(y) n(z) for some y E A and x E B}. Show that if A, B E PSPA ...

298 COMPUTATIONAL COMPLEXITY To satisfy these requirements, we design the machine M* to simulate, on input w, the computation of ...

6.3 Hierarchy Theorems 299 A&, have to be encoded by strings over (0, 1). We recall that, in Section 5.1, the universal DTM ...

300 COMPUTATIONAL COMPLEX1TY sz( Iw’I). For this w’, A4 has enough space to simulate MWj on w’ and to count the number of moves ...

6.3 Hierarchy Theorems 301 B/B, L B/B, R B/B, R B/B, R Figure 6.5: (n + a)” is fully time-constructible. 4.13, where we showed h ...

(1 ) M’ writes 1 on the work tape and moves its tape head to the right of this symbol 1. M’ also moves its tape head of the inpu ...

6.3 Hierarchy Theorems 303 t2 b-4 = 22n, then tz(n) = (tl(n))2 and so limn+&$)log(tl(n))/t2(n) = 0. It follows that P C - DT ...

304 COMPUTATIONAL COMPLEXITY (b) Show that n3 is fully time-constructible. 4. (a) Show that if t(n) is fully time-constructible, ...

6.4 Nondeterministic Turing Machines 305 a b c B S 40, B, L qo qo4,L !Il,hL Ql 421 c, L 42 43,aJ 42,cJ 44, c, L q3 43,aJ 42& ...

306 COMPUTATIONAL COMPlJ3XITY / 0-T \ a6 Figure 6.7: The computation tree of M on input X. a0 = (s, a2baba3ba2bba4@ I- (qo, a2ba ...