CPSC 511 - Introduction to Complexity Theory
CPSC 611 - Complexity Theory
Course Summary
The area of complexity
theory deals with determining the amounts of resources (e.g., time or
space) that are needed to solve a problem, and classifying
computational problems by their difficulty. Understanding the
computational complexity of problems and the limits of efficient
algorithms, prevents computer scientists from searching for
non-existing efficient algorithms. This course will explore
fundamental concepts of complexity theory, such as
- time complexity,
- space complexity,
- the polynomial hierarchy and alternations,
- circuit complexity, and
- complexity theories for randomized algorithms.
Textbooks
- Introduction to the Theory of Computation, Michael Sipser, Thomson Course
Technology, 2nd ed., 2006.
- Computational Complexity: A Modern Approach, Sanjev Arora and Boaz Barak (In
print. A draft
is available online).
Requirements
- CPSC 413
- Interest in theoretical computer science.
Lectures
Time: Tuesdays and Thursdays, 9:30-10:45am.
Location: SH 288
Tutorials
Time: Mondays, 15:00-15:50
Location: ST 063
Forum
News and handouts will be posted to the course forum.
If you have questions that may be interesting to all students, please ask them in the "discussion" section of the forum.
Contact
See my homepage.
Office Hours
- Tuesdays, 10:45-11:30am (SH 288 or ICT 655),
- Mondays, 15:50-16:30 (ST 063 or ICT 655), or
- by appointment.
Please approach me right after class if you want to meet me during my
regular office hours.