Introduction To Complexity Theory

3 credits · Undergraduate Programs

Time and space complexity; the classes P, LOGSPACE, PSPACE and their nondeterministic counterparts; containments and separations between complexity classes; intractability and the theory of NP-completeness; complexity theories for probabilistic algorithms and for parallel algorithms. Prerequisite(s): Computer Science 413. Antirequisite(s): Credit for Computer Science 511 and 611 will not be allowed.