CS 535 Fall 2010 Assignment #4 Date Due: Thursday October 28 at 12 noon Reading: Chapter 7, pages 152-162. Problems : 1. Assume that both A and B are in NTIME (n^{3}). Prove that the union (A union B) and the intersection (A intersect B) are also in NTIME (n^{3}).2. Let f be a polynomial-time computable (partial) function.

a. Explain why, for every x, the set f

^{{-1}}(x) = {y | f(y) = x} is in P.b. Explain why, for every set A in P, f

^{{-1}}(A) = {y | f(y) is in A } is in P.3. Show that 2

^{n}is fully time constructable. That is, show that you can have a TM which, when started on any input x of length h n, runs for exactly 2^{n}steps. (This is just the definition of 2^{n}being fully time constructable.)You need to be precise here, so this one is challenging. You either need to give the TM, including its program, and say why it works (or at least give a convincing example). Or you need to describe for the TM works and again say why.

4. Page 143, Problem 6.21 part 1

5. Page 143, Problem 6.21 part 2.

For these problems you can assume the SAT problem is NP-complete.

6. Page 129, problem 6.5 7. Page 130, problem 6.6