Autumn 2003

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

Problems:

- Closure under union:
- Show if L
_{1}and L_{2}are in P then L_{1}UNION L_{2}is in P. - Show if L
_{1}and L_{2}are in NP then L_{1}UNION L_{2}is in NP.

- Show if L
- Closure under intersection:
- Show if L
_{1}and L_{2}are in P then L_{1}INTERSECT L_{2}is in P. - Show if L
_{1}and L_{2}are in NP then L_{1}INTERSECT L_{2}is in NP.

- Show if L
- Sipser's text Problem 7.10 page 272.
- Sipser's text Problem 7.11 page 272.
- Sipser's text Problem 7.12 page 272
- 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- If f is polynomial-time computable then L
_{f}is in P. - If L
_{f}is in P then f is polynomial-time computable.

- If f is polynomial-time computable then L
- (Bonus) Sipser's text Problem 7.37 page 275