CS 464/664 Assignment 3
Winter 2002
Due: Friday, March 8, 2002 (in class)
- 7.4.3 (a)
- 7.4.3 (b) (ii), (iii), (vi) and (viii)
- 7.4.4
- 7.4.5
- 7.4.7 (this is a tricky question: if you use a reference, cite it
and we will give you 80% of the marks. Otherwise, try it without
using the reference).
- 7.4.8
- 7.4.17
- 8.4.3
- (Bonus for 464, Required for 664)
Prove: If TIME(n) = NTIME(n) then TIME(f(n)) = NTIME(f(n)) for
any proper complexity function f(n). (Hint: If you have a problem
which requires time f(n), how do you make it appear linear).
(Note: You can use the contrapositive form, if you wish, but
I think that is harder than the form presented here).