Computational Complexity

CSE 4115.03 Fall 2009


December 2: Here are some suggested exercises to help study for test.

  • from Sipser, M., Introduction to the theory of computation ,
    7.11, 7.16, 7.17, 7.21, 7.22, 8.6, 8.11, 9.1, 9.6, 9.12

  • from Arora and Barak, Computational Complexity,
    2.7, 2.8, 2.9, 2.14, 5.9a,b

    Please note date of Midterm 3: it will be in class, December 7, 2009. There will not be a final exam.

    Course news will be posted here as needed. Please check frequently (don't forget to refresh), especially right before assignments and tests.

    September 8, 2009:
    Room change: Course location has been changed again by the Registrar's office to Accolade East 012, as announceed in class.


    Prof. Patrick Dymond
    CSE 3052C
    email: last name

    Office hours: after class Wednesday in classroom or in CSEB 3052c (by appointment.)

    Email questions about fairly specific problems are welcome.


    Monday, Wednesday 2:30 in VH 3004

    Important note concerning late enrollment: Late enrollment in this course is not appropriate unless the student has been attending classes since the beginning lectures, and has also been keeping up with the readings and assignments.


    Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

    The main focus of the course is the material from part 1 of the the Arora/Barak (AB) text.
    Familiarity with definitions and other material from automata theory (such as that gained in CSE 2001) is needed.


    CSE 2001, CSE 3101, general fourth-year CSE prerequisites.


    This course is an introduction to the theory of computational complexity. It is intended to give a detailed understanding of the basic concepts of models of computation, computability, and complexity theory. Topics chosen for study include: Turing machine variants and Random Access Machines, the Church-Turing thesis, limits to computation, Turing-recognizable and decidable languages, complexity of resources such as Time and Space, reducibility, simulation, complexity classes, hierarchy theorems, the relationships between P, NP and other classes, NP-completeness, completeness for P, PSPACE and other classes, provable intractability and interactive proof systems. We will also discuss probabilistic computation and applications to parallel computing and/or cryptography if time permits.

    Course Requirements :

    Students attend and participate in the twice-weekly classes, read assigned material from the text in advance of corresponding lectures and prepare individual, well-written answers for assignments and/or exercises. There will be approximately three written assignments. This component counts for 30% of the final grade. There will be two ninety minute in-class tests counting for 25% each, and one final in-class test, counting for 20% of the final grade. These tests are currently scheduled in class on October 19, November 11, and December 7. N.B. If you cannot attend these midterms, you should not enroll in the course. I will provide notice in class and here well in advance of any necessary changes to these dates.

    (Please note that there are no special provisions for making up late exercises, assignments or missed classes or tests. Without sufficient medical documentation that you were both medically unable to perform the required tasks and unable to contact the instructor throughout the period prior to the scheduled date, missed material is assigned a score of zero. If problems arise in meeting a deadline, please contact the instructor by email well in advance. )
    You should avoid plagiarism and fully cite all resources used in preparing your solutions to exercises and assignments. You are allowed to discuss problems with others in the class, but do not make written notes. Prepare your written solution to problems on your own and do not share it with others. Properly acknowledge all sources of help and ideas. Please also read over the department and faculty policies concerning this. Handing in solutions found to be based on the work of others,, or on internet or other external resources leads to serious repercussions.

    Tentative Course Schedule and Readings:

    Please read the material to be covered in each class in advance of the lecture. The readings will be specified in class.

    Assignment due dates will be announced modified here later. I expect Assignment 1 to be due October 7.

    Readings for background: (Please go over this material in the first two or three weeks of term, if not before.)
    Arora&Barak (AB): Ch 0, Appendix A.1

    Lecture 1 (Sept 9): AB: Intro, 0, A1, 1.1, 1.2, 1.3
    Lecture 2 (Sept 14): AB: 1.3, 1.4, Supplemental
    Lecture 3 (Sept 16): AB: 1.5, 1.6
    Lecture 4 (Sept 21): AB 1.6, 1.7
    Lecture 5 (Sept 23): AB: 2.1, 2.2
    Lecture 6 (Sept 28): AB:, 2.3 Lecture 7 (Sept 30): AB: 2.4
    Lecture 8 (Oct 5): AB: 2.4 plus supplemental
    Lecture 9 (Oct 7): AB: 2.5, 2.6, 2.7
    Reading Week (Oct 12-16) - no lectures
    TEST #1 - Monday, Oct 19


    Exercises :

    Some recommended exercises from the text here .


    A list of related reference books.