CISC 876 Computational Complexity (T) Units: 3.00
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. Kai Salomaa.
Offering Faculty: Faculty of Arts and Science