(3 cr.) 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.