# CSEP 590TU Assignment #4Autumn 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 L1 and L2 are in P then L1 UNION L 2 is in P.

2. Show if L1 and L2 are in NP then L1 UNION L 2 is in NP.

2. Closure under intersection:

1. Show if L1 and L2 are in P then L1 INTERSECT L 2 is in P.

2. Show if L1 and L2 are in NP then L1 INTERSECT L 2 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(nk) for some k.

Define the language Lf={< 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 Lf. Show that

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

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

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