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.