CS 535
                                                       Fall 2010

                      Assignment #5


Date Due: Tuesday, November 23 

Reading:   Chapter 5, section 5.1, pages 80-86 and sections 5.4 and 5.5, 
pages 97-117.

Problems :

1. Page 136, #6.11

2. Page 136, #6.12, part 2

3. Page 141, #6.14

4. Page 143, #6.22

5. Page 146, #7.1, parts 3 and 5

6.  A function is a said to be one-way if it is polynomial
time computable but not invertible in polynomial time.


Prove that there exists a one-way function.


(Note: The function f above does not need to be 1-1. However if it is not then
we define its inverse, f -1, to be a function which picks out any
one element in the inverse of f, and gives a special value * if there are none.



7. Let L be a PSPACE-complete language.
Prove that if L is in  NP then NP=PSPACE.