CSE 431 Assignment #5
Spring 2003

Due: Friday, May 16, 2003.

Finish reading chapter 7 of Sipser's text.

Problems

1. Problem 7.6 page 271

2. Problem 7.7 page 271.

3. Problem 7.10 page 272.

4. Problem 7.11 page 272.

5. All the computational problems we have described are defined as languages, i.e. yes/no questions. Given a function f:{0,1}^* -> {0,1}^* we say that f is computable in polynomial time iff there is some TM whose running time is O(n^k) for some k that computes f. Define the language L_i={x | the i-th bit of f(x) is 1}. Show that

   • If f is polynomial-time computable then each L_i is in P.

   • If each L_i is in P then f is polynomial-time computable.
   You should assume for convenience that f always outputs a string of length n when given an input of length n.

   Extra technical condition for the second part: You can also assume that if L_i is in P then there is an efficient algorithm that on input i produces the TM showing that L_i is in P. That is there is a TM M that runs in time polynomial in i that on input i outputs the code of a machine M_i running in polynomial time that accepts L_i.

6. (Bonus) Show that if f is polynomial-time computable then not only is each L_i in P but also that the machine M in the technical condition in problem 5 exists.