## 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 orspace) 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,
- alternative computation models

### Textbook

*Complexity Theory - Exploring the Limits of Efficient Algorithms*, Ingo Wegener, Springer, 1st ed., 2005.
### Requirements

- CPSC 413
- Interest in theoretical computer science.

### Lectures

Time: Tuesdays and Thursdays, 9:30-10:45am.

Location: MS 527
### Tutorials

Time: Wednesdays, 15:00-15:50

Location: ST 057
### 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 and Thursdays, 11:00-11:45am (ICT 655), or
- by appointment.

**Please approach me right after class if you want to meet me during my
regular office hours.**