HW4: Space, Time and Nondeterminism

  1. Let PTIME be the class of languages that can be decided in polynomial time, i.e., for any language L in the class, there is a TM M and an integer k s.t. for every input string x of any length n, M decides whether x \in L in time O(n^k). Show that SPACE(O(\log n)) \subseteq PTIME.
  2. Show that NSPACE(n^2) \subsetneq SPACE(n^5), i.e., a strict subset.
  3. Describe a TM D that takes as input the description of any TM M and input x for M, and simulates M on x and if M halts, it outputs the total number of steps taken in the simulation. What is the time complexity of your D as a function of the time complexity of M?