Time and Space Complexity

Suppose $\lim_{n \rightarrow \infty } t_{1}(n) / n=\infty$. If $t_{1}(n)=t_{2}(n)$ for sufficiently large $n$, then $\operatorname {DTIME}\left(t_{1}(n)\right)=\operatorname {DTIME}\left(t_{2}(n)\right)$.

If $c>1$, then for any $\epsilon >0, \operatorname {DTIME}(c n)=\operatorname {DTIME}((1+ \epsilon ) n$).

Show that if $A, B \in P$, then $A B \in P$.

Show that if $A \in P$, then $A^{*} \in P$.

$\operatorname {PSPACE}\subseteq \operatorname {EXPPOLY}$.

Suppose that $s(n) \geq \log n$. Prove that if a Turing machine halts on all inputs and has a space bound $s(n)$, then it must have a time bound $c^{s(n)}$ for a constant $c$. Use this result to show that, for any $s(n)$, every set in $\operatorname {DSPACE}(s(n))$ is a recursive set.

Show that every finite set of strings belongs to $\operatorname {DTIME}(n)$.

Let $A \in \operatorname {DTIME}(f(n))$ and $B \in \operatorname {DTIME}(g(n))$. Prove that $A \cup B$ and $A \cap B$ are in $\operatorname {DTIME}(\max \left\{ f(n), g(n)\right\} )$. Conclude from these results that the complexity classes $P, \mathrm{PSPACE}, \mathrm{EXP}$ and $\mathrm{EXPPOLY}$ are all closed under Boolean operations union, intersection and complementation.

In the proof of Theorem 6.10, we can actually use nine moves of $M^{\prime }$, instead of ten moves, to simulate at least $m$ moves of $M$. This can be done by merging the fourth and fifth moves into one move. Can you use less than nine moves in $M^{\prime }$ to do the same job?

Estimate how many possible local configurations there are in the proof of Theorem 6.10.

Show that every context-free language is in $P$ (i.e., for every context-free grammar, there is a polynomial-time parsing algorithm).

Show that if $A$ and $B$ are in $\mathrm{PSPACE}$, then $A B$ and $A^{*}$ are also in $\mathrm{PSPACE}$.

Let $A, B \subseteq 1(0+1)^{*}+0$ such that each string $x$ in $A$ or $B$ is a binary representation of a natural number. We let $n(x)$ be the natural number whose binary representation is $x$.