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.