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.


  • H(3-0)


  • Computer Science 413.


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


This course will be offered next in Winter 2024.
Powered by UNITIS. More features.