## 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.**