Computational complexity/hw2

การบ้าน 2 มี 9 ข้อ (optional 2 ข้อ)

1. (AB-4.5) Prove that $\mathrm {2SAT}$ is in $\mathbf {NL}$ .

2. (AB-5.3) Show that if $\mathrm {3SAT}$ is polynomial-time reducible to ${\overline {\mathrm {3SAT} }}$ , then $\mathbf {PH} =\mathbf {NP}$ .

3. (AB-8.1-b) Prove that $\mathbf {IP} \subseteq \mathbf {PSPACE}$ .

4. (AB-8.1-d) Let $\mathbf {IP} '$ denote the class obtained by changing the constant 1/3 in the soundness part of the definition of $\mathbf {IP}$ to 0. Prove that $\mathbf {IP} '=\mathbf {NP}$ .

5. (AB-9.5) Show that if $\mathbf {P} =\mathbf {NP}$ , then one-way functions do not exist.

6. (AB-9.11) Show that if $f$ is a one-way permutation then so is $f^{k}$ (which is $f$ applied $k$ times), where $k=n^{c}$ for some fixed $c>0$ .

7. Consider random variables $Z_{1},Z_{2},\ldots ,Z_{n}$ and let random variable $Z=\sum _{i=1}^{n}Z_{i}$ . We know that when $Z_{i}$ 's are independent, $\mathrm {Var} (Z)=\sum _{i=1}^{n}\mathrm {Var} (Z_{i})$ . Show that the equality still holds when $Z_{i}$ 's are only pair-wise independent.

Hint: Use the definition of variance.

8. (optional) (AB-3.2) Show that $\mathrm {SPACE} (n)\neq \mathbf {NP}$ . (Note that we do not know if either class is contained in the other.)

Hint: See first answers in mathoverflow (and more hints at here). Also this blog post on Sidesplitting proofs.

9. (optional) (AB-8.1-c) Let $\mathbf {IP} '$ denote the class obtained by changing the constant 2/3 in the completeness part of the definition of $\mathbf {IP}$ to 1. Prove that $\mathbf {IP} '=\mathbf {IP}$ .