# 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?