Computer Science

B502 Computational Complexity

Credits: 3

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.

  • Course History

      Fall 2016

      Instructor: Ladislav Novak
      Time: 8:00AM-9:15AM Mon, Wed
      Location: Ballantine Hall, Room 235

      Spring 2012

      Instructor: Steven Myers
      Time: 4:00PM-5:15PM Mon, Wed
      Location: Lindley Hall, Room 008