Homework 4Due March 5

COURSE WEBSITE: www.cs.umd.edu/ gasarch/858/858.html

(there is a tilde before the ``g'' in ``gasarch'')

READING- The three sets of notes- Sparse Sets, PH, and More on Sparse Sets.

1. (10 points) Write your name clearly. Staple the HW so its not loose pages. Where and when will the midterm be? Where and when will the final be?

2. (30 points) Recall that we defined $A\in NP$ by there exists a poly $p$ and a poly predicate $B$ such that

   $A= \{ x \mid (\exists y, \vert y\vert=p(\vert x\vert))[B(x,y)]\}$.

   We define a set $A$ to be in $NX$ if there exists a poly $p$ and a poly predicate $B$ such that

   $A= \{ x \mid (\exists y, \vert y\vert\le p(\vert x\vert))[B(x,y)]\}$.

   Show that $NP=NX$.

3. (30 points) Let $f$ be the function shown in class such that $\phi\in CNF-SAT$ iff $f(\phi)\in CLIQ$. (so $\phi$ is in CNF form and $f(\phi)$ is an ordered pair $(G,k)$ where $G$ is a graph and $k\in\nat$). Let $f_{unl}$ be the modification that outputs an UNLABELLED GRAPH together with a number $k$.
   1. Is $f_{unl}$ 1-1? If it is then prove it. If it is not then give a counterexample (that is, give CNF formulas $\phi\ne \psi$ such that $f_{unl}(\phi)=f_{unl}(\psi)$) AND give a 1-1 function $g_{unl}\in P$ such that $\phi\in CNF-SAT$ iff $g_{unl}(\phi)\in CLIQ$, and $g_{unl}$ returns as its first part an UNLABELLED graph.
   2. Is $f_{unl}$ onto? If it is then prove it. If it is not then give a counterexample (that is, give an ordered pair $(G,k)$, $G$ an UNLABELLED graph, that is NOT in the image of $f_{unl}$).

4. (30 points) NOTATION: if $B$ is a set then $B(x)$ is the function that returns 1 if $x\in B$ and 0 if $x\notin B$. $A\le_{1-tt} B$ is defined as follows. There exists TWO functions $f,b\in P$ such that
   1. $f:\bits * \into \bits *$.
   2. $b:\bits * \into \bit$.
   3. $x\in A$ iff $B(f(x))=b(x)$.

   Show that if there exists a sparse set $S$ such that $SAT\le_{1-tt} S$ then $P=NP$.

5. (Extra Credit) $A\le_{2-OR} B$ if There are $f_1,f_2\in P$ such that (1) $f_1:\bits * \into \bits *$, (2) $f_2:\bits * \into \bits *$, and (3) $x\in A$ iff ( ($f_1(x)\in B$) OR ($f_2(x)\in B)$).

   Show that if there exists a sparse set $S$ such that $SAT\le_{2-OR} S$ then $P=NP$.