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 (n3).
Prove that the union (A union B)  and the intersection (A intersect B) are also in NTIME (n3).


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 2n 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 2n  steps.
(This is just the definition of 2n 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