Computational complexity/hw2

การบ้าน 2 มี xx ข้อ

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

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