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 auxiliary variables ensuring of $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} }$.