Homework 7Due Friday April 9

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

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

1. (0 points) Write your name clearly. Write which HW this is on top of your paper clearly. Staple the HW so its not loose pages. Where and when will the final be?

2. (50 points) (FOR THIS PROBLEM YOU CAN ASSUME THAT $\P\ne\NP$ and $\Sigma_2\ne\Pi_2$ and $\Sigma_3\ne\Pi_3$ etc.) Recall the following (abbreviated) definition of $\AM$.

   Def: Let $\epsilon(n)$ be a monotone decreasing function from $\nat$ to $[0,1]$. A set $A$ is in $\AM(\epsilon(n))$ if there exists polynomials $p,q$, and a poly predicate $V$ such that the following hold.

   Let $x$ be of length $n$.

   $x\in A \implies \Prob_{r\in \bits {p(n)}}((\exists y, \vert y\vert=q(n))[V(x,y,r)=1]) \ge 1- \epsilon(n)$.

   $x\notin A \implies \Prob_{r\in \bits {p(n)}}((\forall y, \vert y\vert=q(n))[V(x,y,r)=0]) \ge 1- \epsilon(n)$.

   1. Does $\AM(\frac{1}{2^n})=\AM(\frac{1}{4})$? Prove or disprove.
   2. Does $\AM(\frac{1}{2^n})=\AM(\frac{1}{2^{n^2}})$? Prove or disprove.

3. (50 points) A PROMISE-AM protocol is an AM-protocol that need only work if the PROMISE about the input is true.
   1. PROMISE: The formula given as input has either $\le 2^{n-2}$ satisfying assignments or $\ge 3\cdot 2^{n-2}$ satisfying assignments. Is there a PROMISE-AM protocol to prove that it HAS $\ge 3\cdot 2^{n-2}$ satisfying assignments? (Either prove there is or say where the attempt at a proof, along the lines of the one about $\gibar$, breaks down.)
   2. PROMISE: The formula given as input has either $\le n^2$ satisfying assignments or $\ge n^2+1$ satisfying assignments. Is there a PROMISE-AM protocol to prove that it HAS $\ge n^2+1$ satisfying assignments? (Either prove there is or say where the attempt at a proof, along the lines of the one about $\gibar$, breaks down.)

4. (Extra Credit- was assigned before but I want you to try harder.) $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$.