Computational complexity/hw1

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

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\cap \{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.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?

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