Computer Science | Computational Complexity
B502 | 28502 | Leivant

(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.