Computer Science 40/240 (Spring 2022) |
 Computer Science Dartmouth College |
When: 10A hour, TTh 10:10-12:00, X-hr F 15:30-16:20
Where: Location TBD
This course introduces students to computational complexity, which is the study of how the resources required to solve a computational problem scale with the problem's size. Central to this theory is the notion of complexity classes, which are sets of computational problems that behave similarly in terms of their resource requirements. By the end of this course, the successful student will have developed a solid understanding for where in a hierarchy — ranging from easy to moderately hard to intractable to unsolvable — a given computational problem falls.
The basic plan is to study five key aspects of computation:
- time,
- space,
- nondeterminism,
- randomness, and
- interaction.
Ideally, a student in this course will have taken an introductory Theory of Computation course, such as Dartmouth's CS 39. In principle, a student with good mathematical maturity can take this course after some self-study to read up on the basics of the Turing Machine model and the notion of NP-completeness (familiarity with these two things will be expected).
There is no set textbook for the course, so it is vital to attend class. However, there are three reference books that cover just about everything we shall do in class, and I will be updating the schedule table above with appropriate references. These reference books are:
- Introduction to the Theory of Computation (Second Edition). Michael Sipser. Referred to above as [Sip].
- Computational Complexity. Christos Papadimitriou. Referred to above as [Pap].
- Complexity Theory: A Modern Approach. Sanjeev Arora and Boaz Barak. Draft available online. Referred to above as [AB].
Other courses taught by Amit Chakrabarti