Spring Semester, 2025
Instructor: John H. Reif
A.
Hollis Edens Professor of Computer Science
Email:
jhreif@gmail.com
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.
The course will cover: Turing
machines, undecidability, recursive function theory, complexity measures,
reduction and completeness, NP, NP-Completeness, co-NP, beyond NP, relativized
complexity, circuit complexity, alternation, polynomial time hierarchy,
parallel and randomized computation, algebraic methods in complexity theory,
communication complexity.
Prerequisites: Computer Science 334 or
equivalent.
Canvas
Website: https://canvas.duke.edu/courses/46396
Detailed
Description of Course Material: see Schedule
Primary Lecture & Discussion Locations:
(See
Schedule for details) Please attend all of these
· Tuesday and Thursday 1:25PM- 2:40PM Biological Sciences 063
· Wednesday 3:05PM- 4:20PM
French Science 4233
·
Backup Discussion Location (only
if announced): Wed Tuesday 3:05PM- 4:20PM
LSRC A155
Reif Office Hours: 1
PM - 3 PM Wednesday
(***Please email Reif a day before to schedule a 1-1 office meeting)
TA:
Qi Dong Email: qi.dong@duke.edu Phone: 9195037620
TA Office hours: Wednesdays and Fridays
from Noon to 1:00 PM(please email to to schedule a 1-1 meeting)
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:
Prerequisites:
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 Schedule for details.
Grading:
Assignments: There will be 6 homework assignments (5% each, 30% total. 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.
Exams: There will be three quizzes (10% each) and an end-term
Final Exam (25%).
Term Papers: There will be a Final Project (15%).
Attendance: Also, attendance and class interaction will provide an
additional 5% of the total grade.
Homework Preparation: 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, nor from generative AI can be utilized or
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.