Computer Science 6743 -- Complexity of Computational Problems, Fall 2008

Announcements | Course information | Important dates | Assignments and tests | Lecture notes


Old announcements


Assignments and tests

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" .


Lecture Notes

A brief list of topics and theorems for the midterm (review sheet).


Course information

Course Information Sheet

Lectures: TBA
Instructor: Antonina Kolokolova , email: [Your browser cannot view this email address] , office ER-6011.
Textbook: M. Sipser: Introduction to the Theory of Computation (second edition).
We will also use lecture notes from similar courses (to be posted later).

Marking scheme (tentative!): 3 assignments 15% each, a midterm %15, a presentation 10%, and a final exam 30%.

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)