CPSC511/611: (Introduction to) Complexity Theory
About These Courses
CPSC 511 is a fourth-year undergraduate course in computational
complexity theory available from the
Department of Computer Science
at the
University of Calgary.
CPSC 611 is a graduate course in the same area.
The
CPSC 511 course outline is available by following this link.
Recommended References
The following references are recommended as sources of additional information
about topics introduced in this course and as introduction to additional
related topics.
- Sanjeev Arora and Boaz Barak
Computational Complexity: A Modern Approach
Cambridge University Press, 2009
Students at the University of Calgary can access this book as an
ebook, without charge,
by following this link.
- Oded Goldreich
Computational Complexity: A Conceptual Perspective
Cambridge University Press, 2008
Students at the University of Calgary can access this book as an
ebook, without charge,
by following this link.
The first of the above references was heavily consulted when preparing
the lecture material that is available on this web site.
Lecture Topics
-
Introduction to These Courses
-
Deterministic Time
-
Nondeterministic Time
-
Space-Bounded Computation
-
Circuit Computations
-
Probabilistic Computation
-
Other Topics
Other Course Information