University of Calgary

CPSC 511 - Introduction To Complexity Theory - Fall 2011

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-1T)

Notes

  • Lectures may run concurrently with Computer Science 611[CPSC611].

Prerequisite(s)

  • Computer Science 413.

Sections

  • LEC 1TR 09:30 - 10:45
    TUT 1W 15:00 - 15:50
This course will be offered next in Fall 2012.
Powered by UNITIS. More features.