Read the fine print1

1.  (35 points, 5 each) For each of the following statements, say whether they are true, false or open according to our current state of knowledge. Briefly justify your answers.

(a)  ISET sp 3SAT (here ISET is the independent set problem).

(b) NL = L.

(c)  TQBF e EXP.

(d) 3SAT sp TQBF.

(e) If P = PSPACE, then NL must be strictly smaller than NP.

(f) Every function f : {0, 1}n → {0, 1} can be computed by a circuit of depth 9n/10. (g) If 3SAT e DTIME(2′n ), then NP EXP.

2.  (20 points) Suppose P = NP.  Show that then there must be a polynomial time algorithm that on input a circuit C of size n, finds an input x such that C(x) = 0, if such an input exists.

3.  (20 points) Given an integer m x n matrix A and an integer column vector b of length m, the 0-1 Integer Programming function is defined as follows: