P: B501. Study of computational complexity classes, their intrinsic
properties, and relations between them. Topics include time and
space computational complexity. Reducibility and completeness of
problems within complexity classes. Complexity of optimization
problems. Complexity hierarchies. Relativization of the P =? NP
conjecture. Parallel computation models and the class NC. B502
corresponds to old C512.