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-8.1-c) (optional) 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}$.

Hint: Use $\mathbf {IP} =\mathbf {PSPACE}$.

Links: การบ้าน 1