COMPSCI 534.01: Computational Complexity

Department of Computer Science

Duke University

John H. Reif

   Spring Semester, 2023

John H. Reif

         A. Hollis Edens Professor of Computer Science

         Class Lectures Location: Building: Gross Hall, Room: 103

         E-mail: reif AT

Summary Description of Course:

Computational Complexity is the study of bounds on the various metrics (such as time and space) of computations executed on abstract machine models (such as Turing machines, Boolean circuits), required to solve given problems, as a function of the size of the problem input.

Detailed Description of Course Material: see Schedule


     Lecture Times:                 12:00 PM – 1:15 PM Tues, Thurs  (See
Schedule for details)
     Lecture Location:            Gross Hall, Room: 103        

Reif Office Hours:               1:30 PM   - 2:30  PM   Tues, Thurs  (***Please email Reif a day before to schedule a 1-1 office meeting with me)

TA: Grayson York MS Graduate Student    TA email:

TA Office hours: 

        Tuesday 4 PM-5 PM Virtual on Zoom (please email to reserve)

        Wends Noon – 1:15 PM in Person at LSRC D344  

Recitation Time and Place by TA:       Thurs 1:15pm-2:30pm Biological Sciences, Room: 63

Course Sakai Site: COMPSCI.534.01.Sp23

Required Text Books:

[Pap]  Christos Papadimitriou. Computational Complexity. Addison-Wesley Longman, 1994. ISBN-10: 0201530821, ISBN-13: 978-0201530827. Corrections: Errata.

[AB] Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press (May 2009), ISBN: 978-0521424264

[G] Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, ISBN: 978-0521884730 (April 28, 2008)

Additional Digital Text Books: ([AB] and [G] used by permission)

Surveys on Computational Complexity:


There are no formal prerequisites for the course, except mathematical maturity.  However, it would help to have a working knowledge of Turing Machines, NP-Completeness, and Reductions, at the level of an undergraduate algorithms class.

Topics: see above Schedule


(Tentative) There will be 6 homeworks (5% each, 30% total), three quizzes (10% each), an end-term Final Exam (20%), and a Final Project  (20%) for the course.  Our policy is that one (and only one) homework during the entire term is allowed not to be handed in, at no loss of credit. Furthermore, if you hand in all the homework, then we will drop the lowest graded homework. Also, attendance and class interaction will provide an additional 5% of the total grade.

Homeworks:  To be prepared using LATEX (preferred) or WORD.

Homework Rules:

·      Be sure to provide enough details to convince, but try to keep your answers to at most one or two pages.

·      It is OK to answer a problem by stating it is open, but if so, please convincingly explain the reasons you believe this.

·      It is permitted to collaborate with your classmates, but please list your collaborators with your homework solution.

·      There is no credit given for homework past their due date.

Honor code: For homework problems, discussion among students is permitted, but students must write up solutions independently on their own. discussion among students is permitted, but students must write up solutions independently on their own. No materials or sources from prior years' classes or from the Internet can be consulted. For details about what is acceptable, see this honesty matrix.

Final Project:

·      The final project is a short (approx. 12 pages) paper over viewing (definition of the problem and terminology, and the details of some part of the proof) a prior result in complexity theory.

·      The topic is of your choice, and the instructor will provide guidance on relevant literature.

·      Novel topics and/or new research may result, but is not necessarily required to still produce an excellent project paper.