Computer Science 511/611 — (Introduction to) Complexity Theory

CPSC 511/611 — (Introduction to) Complexity Theory

Recommended Reference

• Computational Complexity: A Modern Approach — available as an ebook from the University of Calgary library

Topics

1. Introduction and Mathematics Review
2. Deterministic Computation
3. Nondeterministic Computation
4. Space-Bounded Computation
5. Alternating Turing Machines and the Polynomial Hierarchy
6. Circuit Complexity
7. Randomized Computation
8. Other Topics

Other Course Information

• Information about Assignments
• Information about CPSC 511 Tests
• Information about the CPSC 611 Project

cpsc 511/611 computer science faculty of science u of c

CPSC 511/611 introduction to cpsc 511/611 deterministic computation nondeterministic computaton space-bounded computation alternation circuit complexity randomized computation other topics assignments cpsc 511 tests cpsc 611 project