University of Calgary

CPSC 511 - Introduction To Complexity Theory - Winter 2022

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.
This course may not be repeated for credit.

Hours

  • H(3-0)

Prerequisite(s)

  • Computer Science 413.

Antirequisite(s)

  • Credit for Computer Science 511 and 611 will not be allowed.

Sections

Powered by UNITIS. More features.