B502 Computational Complexity
Prerequisite(s): CSCI-B 501.
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.
Instructor: Ladislav Novak
Time: 8:00AM-9:15AM Mon, Wed
Location: Ballantine Hall, Room 235
Instructor: Steven Myers
Time: 4:00PM-5:15PM Mon, Wed
Location: Lindley Hall, Room 008