|Announcements |||Course information |||Important dates |||Assignments and tests |||Lecture notes|
|Assignment 1. Due Oct 9, 2007.||Assignment 2. Due Oct 30, 2007.||Assignment 3. Due Nov 27, 2007.|
For typesetting please use LaTeX. A good introduction to LaTeX is "Essential LaTeX" .
A brief list of topics and theorems for the midterm (review sheet).
Description: The goal of this course is to help students develop an intuitive feel for hardness of computational problems, and an ability to prove that intuition. What does it mean that a given problem is "hard"? In which sense is it "hard": is it memory-intensive, computation-intensive; how are these notions related? How expressive are various languages used in databases and AI, and what does it mean computationally? These are some of the questions we will explore in this course.
In particular, we will cover the classical P vs. NP problem (is checking a solution easier than finding a solution? Nobody knows!), as well as classes of higher complexity (polynomial-time hierarchy), space classes, counting classes, randomized and circuit complexity, and descriptive and proof complexity. We will also review some computability theory and, time permitting, cover a range of advanced topics such as PCP, natural proofs (why it is hard to resolve the P vs. NP question), hardness of approximation, etc.
(this picture is from the cover of the book "Descriptive Complexity" by Neil Immerman)