Homework 5Due March 15

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. Write which HW this is on top of your paper clearly. Staple the HW so its not loose pages. Where and when will the midterm be? Where and when will the final be?

2. (60 points) Let $S$ be such that, $(\forall n)[\vert S\cap \bits {\le n}\vert \le n^{\log n}]$.
   1. Assume $SAT \le_m^p S$. What can we conclude?
   2. Assume $SAT \le_T^p S$. What can we conclude?
   (You may need to define some new terms to state what you can conclude.)

3. (30 points) Show that if $\Sigma_2^p=\Pi_2^p$ then, for all $i\ge 2$, $\Sigma_i^p = \Sigma_2^p$.