Computational Complexity (Spring 2009)

This course describes attempts to answer a fundamental question of CS namely: What can computers solve efficiently?

Some Bibliography:

While the course does not follow one book in a precise order, most of the material can be found in the following two books (that are available online). I will point to relevant section in the books when teaching the material.

Some of the topics (at least in the beginning of the course) are also covered in the following books.


Exercise are given so that you can make sure that you understand the material. Submitting the exercises is not mandatory. I will check a small sample of the questions in each exercise and will give grades. The exercise grade will be 10% of the final grade. (The exercise grade will not be used if it reduces the final grade.