Computational complexity/hw1

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

1. (AB-1.7) Define a two-dimensional Turing machine to be a TM where each of its tapes is an infinite grid (and the machine can move not only Left and Right, but also Up and Down). Show that for every (time-constructible) $T:{\mathbb {N} }\rightarrow {\mathbb {N} }$ and every Boolean function $f$, if $f$ can be computed in time $T(n)$ using a two-dimensional TM then $f\in DTIME(T(n)^{2})$.

2. (AB-2.17, 1st half) In the Exactly One 3SAT problem, we are given a 3CNF formula $\phi$ and need to decide if there exists a satisfying assignment $u$ for $\phi$ such that every clause of $\phi$ has exactly one True literal. Prove that Exactly One 3SAT is NP-complete.

Hint: Replace each occurrence of a literal $v_{i}$ in a clause $C$ by a new variable $z_{i,C}$ with additional clauses and auxiliary variables ensuring that if $v_{i}$ is TRUE, then $z_{i,C}$ can be either TRUE or FALSE, but if $v_{i}$ is FALSE, then $z_{i,C}$ must be FALSE.

3. (AB-2.23) Prove that $\mathbf {P} \subseteq \mathbf {NP} \cap \mathbf {coNP}$

4. (AB-6.8) A language $L\subseteq \{0,1\}^{*}$ is sparse if there is a polynomial $p$ such that $|L\cup \{0,1\}^{n}|\leq p(n)$ for every $n\in {\mathbb {N} }$. Show that every sparse language is in $\mathbf {P} _{\mathrm {/poly} }$.

5. (AB-7.6) (a) Prove that a language $L$ is in $\mathbf {ZPP}$ iff there exists a polynomial-time PTM $M$ with output in $\{0,1,?\}$ such that for every $x\in \{0,1\}^{*}$, with probability 1, $M(x)\in \{L(x),?\}$ and $\mathbf {Pr} [M(x)=?]\leq 1/2$.

(b) Show that $\mathbf {ZPP} =\mathbf {RP} \cap \mathbf {coRP}$

6. (AB-7.5) Recall that, in lecture, we briefly state that one can simulate a coin with head probability $p$, if the real number $p$ is efficiently computable. Let us study to what extent this claim truly needs the assumption that $p$ is efficiently computable. Describe a real number $p$ such that given a random coin that comes up "Heads" with probability $p$, a Turing machine can decide an undecidable language in polynomial time.

Hint: Think of the real number $p$ as an advice string. How can its bits be recovered?