Problem Solving in Automata, Languages, and Complexity

6.4 Nondeterministic Turing Machines 307 such an algorithm a guess-and-verify algorithm. We will see more examples of such algor ...

308 COMPUTATIONAL COMPLEXITY Time and Space Complexity of NTM’s. Now, we define the notion of time and space complexity of an NT ...

6.4 Nondeterministic Turing Machines 309 NP = U NTIME(n”). 00 NPSPACE = U NSPACE(n”). c>o The following results are analogous ...

310 COMPUTATIONAL COMPLEXITY 2c’s(n) and so we need 2 ‘*‘W bits to record the current computation path under simulation. Instead ...

6.4 Nondeterministic Turing Machines 311 Proof NP C - NPSPACE = PSPACE.^0 We now apply Savitch’s theorem to get some weak space ...

312 COMPUTATIONAL COMPLEXITY NPSPACE = PSPACE I I w if EXP __r--, EXPPOLY Figure 6.8: Inclusion relations between complexity cla ...

6.4 Nondeterministic Turing Machines 313 0 * 2. (a) 0 ( ) C L2 = (21cx2c l l *cx&2cy 1 Xl,.. .,xm,y E {U,b}‘,(3il,.. .,ik) [ ...

(^314) COMPUTATIONAL COMPLEXITY 6.5 Context-Sensitive Languages In this section, we study a restricted type of grammars and pres ...

6.5 Context-Sensitive Languages 315 Solution 2. A more general technique of converting an unrestricted grammar to a context-sens ...

316 COMPUTATIONAL COMPLEXITY Example 6.34 Find a context-sensitive grammar for the language L = {an2 1 n > - 1). Solution. Fo ...

6.5 Context-Sensitive Languages 317 Theorem 6.35 The class of context-sensitiue languages is exactly the class NSPACE(n). Proof. ...

318 COMPUTATIONAL COMPLEXITY Conversely, let L E AKPA GE(n). W e may assume that there is a one- tape NTM M1 that accepts L whos ...

6.5 Context-Sensitive Languages 319 for all a E C, where generates exactly the Lh is a new nonterminal symbol. Then, grammar G2 ...

320 COMPUTATIONAL COMPLEXITY length < s(n) + [lognl + [IQ11 + 2. It is easy to see that we can define a linear ordering 4 ove ...

6.5 Context-Sensitive Languages 321 reachable from ,& Assume that & has been computed correctly. Then, in the computatio ...

322 COMPUTATIONAL COMPLEXITY * 5. What is wrong if we use the following simpler algorithm to compute IVk inthe proof of Theorem ...

References Aho, A., Hopcroft, J. and Ullman, J. (1974) The Design and AnaZysis of Computer Algorithms, Addison-Wesley, Reading, ...

388 REFERENCES Karp, R. M. (1972), Reducibility among combinatorial problems, in Compkx- ity of Computer Computations, Miller, R ...