Homework 3

This homework covers the material from lectures 11 to 15.

Due date: November 15th, 10pm Waterloo time.

Required Exercises

Problem 1 - Another way to detect languages in $\mathsf{BPP}$ (20 points)

Let $M$ be a poly-time PTM and let $C$ be a language where, for some fixed $0<{\epsilon }_1<{\epsilon }_2<1$, we have that $$x\notin C\Rightarrow \underset{r}{Pr}[M(x,r)=1]\le {\epsilon }_1,$$ and $$x\in C\Rightarrow \underset{r}{Pr}[M(x,r)=1]\ge {\epsilon }_2.$$

Prove that $C$ is in $\mathsf{BPP}$.

Problem 2 - Zero-error probabilistic polynomial time ($\mathsf{ZPP}$) (20 points)

Define the complexity class $\mathsf{ZPP}$ as the class of languages $L$ for which there exists a poly-time PTM $M$ which has three possible outputs $0$, $1$, and $\mathrm{\perp }$, where, on any input $x$, we have:

• $\underset{r}{Pr}[M(x,r)\in \{L(x),\mathrm{\perp }\}]=1$, that is, $M$ never outputs the wrong answer; and
• $\underset{r}{Pr}[M(x,r)=\mathrm{\perp }]\le 1/2$.

Prove that $\mathsf{ZPP}=\mathsf{RP}\cap \mathsf{coRP}$.

Problem 3 - Interactive Proofs (20 points)

Let $\mathsf{MAM}$ be the class of languages $L$ which are $1/3$-decided by a Merlin-Arthur-Merlin protocol, where Merlin first sends a message to Arthur, then Arthur sends a message to Merlin, and finally Merlin sends another message to Arthur, and then Arthur decides (deterministically) whether to accept or reject. (Remember, Arthur can only use randomness to send his message to Merlin.)

Prove that $\mathsf{MAM}=\mathsf{AM}$.

Hint: probabitity amplification.

Problem 4 - Space and Time (20 points)

Prove that $\mathsf{BPL}\subseteq \mathsf{P}$.

Problem 5 - Logspace reductions (20 points)

Let

$$\mathsf{NON}\mathsf{-}\mathsf{BIPARTITE}=\{⟨G⟩\mid G\text{ is not a bipartite graph}\}.$$ and $$\mathsf{st}\mathsf{-}\mathsf{UCONN}=\{⟨G,s,t⟩\mid G\text{ is an undirected graph with a path from }s\text{ to }t\}.$$

Prove that $\mathsf{NON}\mathsf{-}\mathsf{BIPARTITE}{\le }_L\mathsf{st}\mathsf{-}\mathsf{UCONN}$.

Hint: From a graph $G(V,E)$, construct a new graph $H(V_1\bigsqcup V_2,F)$, where for every $v\in V$, we have a copy $v_1\in V_1$ and $v_2\in V_2$, and where $F:=\{\{u_1,v_2\},\{u_2,v_1\}\mid \{u,v\}\in E\}$. Now, note that $G$ is not bipartite if and only if there is a path in $H$ from $u_1$ to $u_2$ for some $u\in V$. Use this idea to construct your logspace reduction.

Also, remember that a graph is bipartite if and only if it has no odd cycles.