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

$$\mathtt{\text{STRONGLY-CONNECTED}}:=\{⟨G⟩\mid G\text{ is a strongly connected directed graph}\}.$$

Prove that $\mathtt{\text{STRONGLY-CONNECTED}}$ is NL-complete.

Problem 2 - Space, Time and Padding (20 points)

Let $\mathrm{\Sigma }$ be a finite alphabet, and $\mathrm{\#}\notin \mathrm{\Sigma }$ be a special symbol.

Let $\mathtt{\text{pad}}:{\mathrm{\Sigma }}^{\ast }\times \mathbb{N}\to {\mathrm{\Sigma }}^{\ast }{\mathrm{\#}}^{\ast }$ be the padding function defined as follows: given any string $x\in {\mathrm{\Sigma }}^{\ast }$ (of length $n$) and any integer $m$, $\mathtt{\text{pad}}(x,m):=x{\mathrm{\#}}^a$, where $a:=max(m-n,0)$. Thus, $\mathtt{\text{pad}}(x,m)$ is a string of length $m$ obtained by appending the appropriate number of $\mathrm{\#}$ symbols to $x$.

For any language $A$ and any function $f:\mathbb{N}\to \mathbb{N}$, let $$\mathtt{\text{pad}}(A,f):=\{\mathtt{\text{pad}}(x,f(|x|))\mid x\in A\}.$$

Prove the following:

1. For every language $A$ and every natural number $c$, $A\in \mathtt{\text{P}}$ if and only if $\mathtt{\text{pad}}(A,n^c)\in \mathtt{\text{P}}$.

2. Prove that $\mathtt{\text{P}}\ne \mathtt{\text{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 \mathtt{\text{SPACE}}(f(n))$ but $A\notin \mathtt{\text{SPACE}}(o(f(n)))$.

A function $f:\mathbb{N}\to \mathbb{N}$ is space-constructible, where $f(n)=\mathrm{\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 $\mathtt{\text{PH}}=\mathtt{\text{PSPACE}}$, then the polynomial hierarchy has only finitely many levels (i.e., it collapses).

Problem 4 - BPP and PSPACE (20 points)

Prove that $\mathtt{\text{BPP}}\subseteq \mathtt{\text{PSPACE}}$.

Problem 5 - Another PSPACE-complete language (20 points)

Prove that the following language is PSPACE-complete:

$$\mathtt{\text{IN-PLACE-ACCEPTANCE}}:=\{⟨M,x⟩\mid M\text{ is a TM that accepts }x\text{ without using any extra space}\}.$$

Remark: Note that the TM $M$ is allowed to use (i.e., read/write) on the input tape, but it cannot/should not use any extra space (i.e., it cannot use any other tape).