Homework 2Due Feb 18

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

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

1. (5 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. (20 points) Show that if $A\le_m^p B$ and $B\in P$ then $A\in P$.

3. (25 points) Let $UNIQ$ be the following set of Boolean formulas.

   $UNIQ=\{ \phi \mid \phi\hbox{ has EXACTLY one satisfying assignment } \}.$

   1. Write $UNIQ$ in terms of quantifiers and a poly predicate.

   2. Show that if $UNIQ\in P$ then $P=NP$.

4. (25 points) Assume that there exists a function $f$ with domain Boolean formulas and range $\bits *$ (interpreted as assignments to the formula, so a formula on $n$ variables goes to an element of $\bits n$) such that

   1) If $\phi\in SAT$ then $f(\phi)$ is a satisfying assignment for $\phi$.

   2) If $\phi\notin SAT$ then $f(\phi)$ will still be an assignment, but we do not guarantee anything about it.

   Show that, under this assumption, $P=NP$.

5. (25 points) Let $A\in NP$ via $B\in P$ and polynomial $p$. That is

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

   Show that if $P=NP$ then there exists a function $f\in P$ with the following behaviour:

   If $x\in P$ then $f(x)=y$ such that $B(x,y)$ (so $f$ produces the witness).

   If $x\notin P$ then $f(x)=NO$ (so $f$ declares there is no witness).

6. (EXTRA CREDIT) Let

   
   

   $$f(k) = \cases { k^2 & if $SAT\in DTIME(n^k)$; \cr k & if $SAT\notin DTIME(n^k)$. \cr }$$
   
   

   We are pondering if $f$ can be computed in poly time. SAY which of the following is true and prove it:

   (a) It is KNOWN that $f\notin P$.

   (b) It is KNOWN that $f\in P$.

   (c) The status of $f$ in $P$ is not known- it is linked to the $P=NP$ question.