CSEP 590TU Assignment #4
Autumn 2003

Due: Wednesday, October 29, 2003.

Read chapter 7 of Sipser's text, sections 7.1-7.3.

Problems:

1. Closure under union:

   1. Show if L₁ and L₂ are in P then L₁ UNION L ₂ is in P.

   2. Show if L₁ and L₂ are in NP then L₁ UNION L ₂ is in NP.

2. Closure under intersection:

   1. Show if L₁ and L₂ are in P then L₁ INTERSECT L ₂ is in P.

   2. Show if L₁ and L₂ are in NP then L₁ INTERSECT L ₂ is in NP.

3. Sipser's text Problem 7.10 page 272.

4. Sipser's text Problem 7.11 page 272.

5. Sipser's text Problem 7.12 page 272

6. 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 that computes f whose running time is O(n^k) for some k.

   Define the language L_f={< x,i,b > | the i-th bit of f(x) is b}. Note that if f(x) has length m then neither < x,m+1,0 > nor <x,m+1,1 > will be in L_f. Show that

   1. If f is polynomial-time computable then L_f is in P.

   2. If L_f is in P then f is polynomial-time computable.

7. (Bonus) Sipser's text Problem 7.37 page 275