HW#3 --- last modified January 01 1970 00:00:00..
Due date: Mar 21
Purpose:
To learn about the relationship among various space and time
complexity classes. To learn about the hierarchy theorem, reductions between
classes, hardness and completeness.
Specification:
Do the following problems out of Papadimitriou: 7.4.3, 7.4.7, 7.4.8, 8.4.3, 9.5.2.
Point Breakdown
2pts each problem |
10pts
|
Total |
10pts |
|