Date Due : Tuesday, November 10
Reading: Chapter 6, pages 122-142
Problems :
1. Assume T is a deterministic 1 tape TM with q states, 17 input symbols, and t tape symbols. (Here q,t are integers.) Furthermore assume that on any input n, T never visits more than n2 tape squares. How many different possible ID's does T have on an input of length n. Briefly explain your reasoning.
2. Prove that L is contained in P.
3. (i). Prove that TIME (n2) is closed under difference. That is, if A and B are both in TIME (n2) then so is A-B.
(ii). It is easy to prove that TIME (n2) is closed under complement. But it is not known if NTIME(n2) is also closed under complement. What goes wrong with the usual "reverse accepting and rejecting" proof that TIME (n2) is closed under complement when you try to do the same form NTIME(n2).
4. Let f: N --> N be a function computable in TIME(n4) and let g: N --> N be a function computable in TIME(n3).
(i) Show that f(g(x)) (That is f composed with g) can be computed in time (n12).
(ii) What is the smallest k such that you can show that f*g(x) = f(x)*g(x) can be computed in time (nk) ? Justify your answer.
5. A tally language (page 113 of the book) is just a language L which is a subset of {1*}.
(i). Assume that L is a set of integers which is in TIME (2n). Define T the tally version of L to be T = {1n | n is in L}. Prove that T is in TIME (n).
(ii). Can you similarly show that if L is in NTIME (2n) then T (as defined in part (i)) is in NTIME (n) ? Why or why not.
6. Assume that both A and B are in NSPACE (n3). Prove that (A intersect B) is also in NSPACE (n3).
7. (i). Problem 5.1 - first part only - on page 80. That is, prove that log n in o(n)
8. Show that 2n is fully time constructible. That is, show that you can have a TM which, when started on any input x of length n, runs for exactly 2n steps. (This is just the definition of 2n being fully time constructible.)
9. Consider the definition that a function f being computed by a time or space bounded deterministic transducer. (See the bottom of page 76 of the textbook.)
Assume that L is defined by a computable relation R(x,y) such that x is in L iff there exists a y where |x| = |y| and R(x,y) holds, furthermore that the relation R is decidable in TIME(n log n). (Here n = |x|+|y|.)
Show that L is in SPACE (n log n).