Complexity Theory

3 credits · Graduate Programs

Deterministic and non-deterministic time and space complexity; complexity classes and hierarchies; NP-complete problems and intractable problems; axiomatic complexity theory. Antirequisite(s): Credit for Computer Science 611 and Computer Science 511 will not be allowed. Notes: Computer Science 413 or equivalent is recommended as preparation for this course.