Homework 4
This homework covers the material from lectures 1 up to 20.
Due date: November 30th, 10pm Waterloo time.
Problem 1 - More NL-completeness (20 points)
Recall that a directed graph is strongly connected if there is a directed path from every vertex to every other vertex. Let
$$ \texttt{STRONGLY-CONNECTED} := \{ \langle G \rangle \mid G \text{ is a strongly connected directed graph} \}. $$
Prove that $\texttt{STRONGLY-CONNECTED}$ is NL-complete.
Problem 2 - Space, Time and Padding (20 points)
Let $\Sigma$ be a finite alphabet, and $\# \notin \Sigma$ be a special symbol.
Let $\texttt{pad} : \Sigma^{*} \times \mathbb{N} \to \Sigma^{*} \#^{*}$ be the padding function defined as follows: given any string $x \in \Sigma^*$ (of length $n$) and any integer $m$, $\texttt{pad}(x,m) := x \#^{a}$, where $a := \max(m-n,0)$. Thus, $\texttt{pad}(x,m)$ is a string of length $m$ obtained by appending the appropriate number of $\#$ symbols to $x$.
For any language $A$ and any function $f : \mathbb{N} \to \mathbb{N}$, let $$\texttt{pad}(A,f) := \{ \texttt{pad}(x,f(|x|)) \mid x \in A \}.$$
Prove the following:
-
For every language $A$ and every natural number $c$, $A \in \texttt{P}$ if and only if $\texttt{pad}(A,n^c) \in \texttt{P}$.
-
Prove that $\texttt{P} \neq \texttt{SPACE}(n)$.
Hint: for the second part, you can use the space hierarchy theorem, which states that for any space-constructible function $f : \mathbb{N} \to \mathbb{N}$, there exists a language $A$ such that $A \in \texttt{SPACE}(f(n))$ but $A \notin \texttt{SPACE}(o(f(n)))$.
A function $f : \mathbb{N} \to \mathbb{N}$ is space-constructible, where $f(n) = \Omega(\log n)$, if the function that maps $1^n$ to the binary representation of $f(n)$ can be computed by a Turing machine using $O(f(n))$ space.
Problem 3 - PH and PSPACE (20 points)
Show that if $\texttt{PH} = \texttt{PSPACE}$, then the polynomial hierarchy has only finitely many levels (i.e., it collapses).
Problem 4 - BPP and PSPACE (20 points)
Prove that $\texttt{BPP} \subseteq \texttt{PSPACE}$.
Problem 5 - Another PSPACE-complete language (20 points)
Prove that the following language is PSPACE-complete:
$$ \texttt{IN-PLACE-ACCEPTANCE} := \{ \langle M, x \rangle \mid M \text{ is a TM that accepts } x \text{ without using any extra space} \}. $$