A systematic studyof the known relations between the most important resource bounded complexity classes. Reductions, separation results and translation techniques. Relativized computation. Topics may include also: Circuit complexity, Kolmogorov-Chaitin complexity, Communication complexity. Three term-hours; lectures and seminars.
S Permission of the School. CISC 365 (or equivalent) is recommended.