Homework 8Due Friday April 21

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

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 each $k=1,2,3,\ldots$ try to do the proof that $\SAT \le_r^p \SAT_k$, modeled after the proof that $\SAT \le_r^p \SAT_{12}$. For which $k$ does the proof work out nicely (perhaps with minor modification)? For which $k$ does the proof not work out? What step breaks down?

3. (50 points) Let

   $\SAT_{i,j} = \{ \phi \st \char93 (\phi) \equiv i \pmod j \}$

   Let $i,j$ be constants. Show that if $\SAT_{i,j} \in \P$ then $\SAT\in \R$.

4. (0 points- do not hand in, but do for your own benefit)
   1. Write down a Boolean Formula $\phi(x_1,x_2,y_1,y_2)$ such that $\phi(a,b,c,d)$ is true iff $(a,b) \preceq (c,d)$ where $\preceq$ is the lex ordering.
   2. Give an algorithm that will, given $n$, construct a Boolean Formula $\phi(x_1,\ldots,x_n,y_1,\ldots,y_n)$ such that $\phi(a_1,\ldots,a_n,b_1,\ldots,b_n)$ is true iff $(a_1,\ldots,a_n)\preceq (b_1,\ldots,b_n)$. Your algorithm should run in time $p(n)$ for some polynomial $n$.