Computational Complexity

Suppose we are given three pegs and $n$ disks, with all $n$ disks having different size. Initially, the $n$ disks are stacked in decreasing size, from bottom to top, in the first peg (see Figure 6.1). The Tower of Hanoi problem is to transfer the entire tower of $n$ disks from the first peg to the second peg, moving one disk at a time and never putting a larger disk on top of a smaller disk. What is the fastest solution to this problem? Is the fastest solution feasible for size $n=64$ (the size of the original Tower of Hanoi problem)?

Figure 6.1: The Tower of Hanoi problem.

Show that the function $2^{\sqrt{\log n}}$ grows slower than every function in the polynomial sequence, but faster than every function in the poly-log sequence.

Suppose $f(n) \prec g(n)$. Show that there exists a function $h(n)$ such that $f(n) \prec h(n) \prec g(n)$.

Show that $\log^{*} n \prec \log^{(m)} n$ for any constant integer $m \geq 1$.

Show that $2^{\ln n}=o(n)$ and $2^{\log (2 n)}=O(n)$.

Show that $(\log n)^{10} \prec n^{10} \prec 2^{(\log n)^{10}}$.

Compare the following three functions using the $\prec$ notation:

Compare $2^{\log { }^{*} n}$ with $n$ using the $\prec$ notation.

Suppose that $f(n) \prec g(n)$. Is it true that for any increasing function $h(n)$ with $\lim_{n \rightarrow \infty } h(n)=\infty , h(f(n)) \prec h(g(n))$? Present a proof or a counterexample.

Prove that $\log^{(k+1)} \prec \log^{(k)} n$ for any $k \geq 0$.

Denote $\log^{* *} n=\min \left\{ k \mid \left(\log^{*}\right)^{(k)} n \leq 1, k \geq 1\right\}$. Compare $\log^{* *} n$ with $\log^{*} n$.

Recall the Ackermann function $A$ defined in Exercise 8 of Section 4.8.

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$.

Show that $(n+2)^{2}$ is fully time-constructible.

Show that $\lceil \sqrt{n}\rceil$ is fully space-constructible.

$\quad P \underset {\neq }{\subset } \mathrm{EXP}$.

$\mathrm{EXP} \neq \mathrm{PSPACE}$.

Describe the detail of the 3-worktape DTM $M^{*}$ of Theorem 6.16. In particular, describe how $M^{*}$ works using input $w$ as both the machine code for $M_{w}$ and as the input to $M_{w}$, while it is stored in the read-only input tape.

In the proof of Theorem 6.17, we used the dovetailing technique to perform the parallel simulation of $M_{w}$ and $M^{c}$. Can we use, instead, the product Turing machine method of Example 5.9 to perform the parallel simulation?

Assume that $A \leq_{m} B$ by a reduction function $f$ with time bound $2^{n}$. Also assume that $B \in \operatorname {DTIME}(2^{n})$. What can you say about the time complexity of set $A$?

Show that $\operatorname {DSPACE}\left(n\left(\log^{*} n\right)^{100}\right) \stackrel{\subset }{\neq } \operatorname {DSPACE}(n \log n)$.

Show that EXP $\underset {\neq }{\subsetneq }$ EXPPOLY.

Show that PSPACE $\underset {\neq }{\cup } \bigcup_{c>0} \operatorname {DSPACE}\left(2^{c n}\right)$.

Let $L=\left\{ a^{i_{1}} b a^{i_{2}} b \cdots b a^{i_{k}} b b a^{j} \mid i_{1}, \ldots , i_{k}, j>0, \sum_{r \in A} i_{r}=j\text{ for some }A \subseteq \left\{ 1,2, \ldots , k\right\} \right\}$. Find an NTM accepting the language $L$.

Show that $\operatorname {NSPACE}(n) \underset {\neq }{\subseteq } \operatorname {NSPACE}(n^{2} \log n)$.

Show that $\operatorname {NSPACE}(n) \underset {\neq }{\subseteq } \operatorname {NSPACE}\left(n^{1.5}\right)$.

Construct multi-tape NTM's to accept the following languages in time $t(n)=2 n$ :

In the proof of Theorem 6.27, the predicate $\operatorname {reach}\left(\alpha_{1}, \alpha_{2}, 2^{i}\right)$ was solved by a deterministic recursive algorithm. Convert it to an equivalent nonrecursive algorithm that uses space $O\left((s(n))^{2}\right)$.

Show that the complexity class NP is closed under union, intersection, concatenation and Kleene closure.

Show that, for any real numbers $r \geq 1$ and $0<\epsilon <1$,

Show that if $t_{1}(n), t_{2}(n)$, and $f(n)$ are fully time-constructible functions with $t_{2}(n) \geq n$ and $f(n) \geq n$, then $\operatorname {NTIME}\left(t_{1}(n)\right) \subseteq \operatorname {NTIME}\left(t_{2}(n)\right)$ implies $\operatorname {NTIME}\left(t_{1}(f(n))\right) \subseteq \operatorname {NTIME}\left(t_{2}(f(n))\right)$.

Show that if $P=\mathrm{NP}$, then

Find a context-sensitive grammar for the language

Find a context-sensitive grammar for the language

Construct context-sensitive grammars for the languages of Examples 4.17 and 4.18, and for the languages in Exercises 3(b)-3(i) of Section 4.5.

Complete the last part of the proof of Theorem 6.35. That is, describe how to attach the leftmost and rightmost blanks to their neighboring symbols to convert grammar $G_{2}$ to a context-sensitive grammar.

Show that the class of context-sensitive languages is closed under union, intersection, concatenation, and Kleene closure.

Find a recursive language $L$ that is not context-sensitive.

What is wrong if we use the following simpler algorithm to compute $N_{k}$ in the proof of Theorem 6.36?

For each $k$, to compute $N_{k}$, we generate each configuration $\alpha \in C_{x}$ one by one and, for each one, nondeterministically verify whether $\operatorname {reach}(\beta , \alpha , k)$ (by machine $M_{1}$), and increments the counter for $N_{k}$ by one if $\operatorname {reach}(\beta , \alpha , k)$ holds.

Recall, from Exercise 6 of Section 3.5, the notion of 2-stack PDA's. Show that each language accepted by a 2 -stack PDA is a context-sensitive language.