COMP 506: Introduction to Complexity Theory

prerequisites: COMP 330 or COMP 360

calendar description: (3 credits 3 hours) The study of computational complexity and intractability: Cook's Theorem, NP-completeness, oracles, the polynomial time hierarchy, lower bounds, heuristics, approximation problems.