EECS 4115/5115, Fall 2025
EECS 4115/5115
Computational Complexity
Fall 2025
Web page contents:
General Information
Announcements
Important Dates
Resources
Reading
Course Handouts
General Information
Instructor: Eric Ruppert
Email: eruppert (a) yorku.ca (Please use a York email account when sending me email, and start your subject line with [4115] or [5115].)
Lectures: Mondays and Wednesdays from 11:30 to 13:00 in room 107 of the Life Sciences Building.
Professor's Office Hours: Mondays 16:00-17:00 and Thursdays 14:30-15:30 in room 3052 of the Lassonde building. If you want to see me at another time, drop by or send me email to arrange an appointment.
Course Overview
This course is intended to introduce students to the fundamentals of complexity theory, which is an important part of the foundations of the entire field of computer science.
We'll look at models of computers (e.g. Turing machines) and see how they are used to measure the resources (time, space and others) required to solve problems. If we pick a model and a bound on one or more resources, we can define a complexity class (e.g. P, NP, NC) to be the set of problems that can be solved in that model with the given resources. These classes give us a systematic way of understanding how efficiently problems can be solved.
In studying complexity theory, we learn about techniques that can be used to design efficient algorithms. We also learn how to identify those problems for which efficient solutions do not exist or are unlikely to exist. Such information is useful, because it often suggests how to modify our approach when faced with an intractable problem: for example, we might look for approximate solutions instead of exact solutions, or try to solve a special case of the problem that is sufficient for our needs.
This course assumes knowledge of the material in CSE2001 and CSE3101, and you should be comfortable reading and writing mathematical proofs.
Here is a tentative list of topics:
- Models of computation: various types of Turing Machines, Random Access Machines
- Definitions of some basic complexity classes (LOGSPACE, P, NP, coNP, PSPACE) & relationships between them
- Time & space hierarchy theorems
- Reductions, NP-completeness
- Parallel computation (circuits, Parallel Random Access Machines, NC, P-completeness)
- An introduction to randomized computation (time permitting)
Marking scheme
| Component | EECS4115 | EECS5115 |
| Homework exercises | 15% | 15% |
| Test 1 | 15% | 15% |
| Test 2 | 15% | 15% |
| Test 3 | 15% | 15% |
| Project (EECS5115 only) | 0% | 10% |
| Final exam | 40% | 30% |
Academic Honesty
The key to academic honesty for this course is simply this: Solutions that you submit should be your own work.
Although you may discuss the general approach to solving an assignment problem
with other people, you should not discuss the solution in detail.
You must not take any written notes away from such a discussion.
Also, you must list on the cover page of your solutions any
people with whom you have discussed the problems.
The solutions you hand in should be your own work. While
writing them, you may use course materials and your own
lecture notes but no other outside sources.
It is not acceptable to try to find the answer to a homework question on the web or using AI tools (such as LLM-based software), put it in your own words and submit it. You may learn a little by doing this, but you will learn much, much more by working on the problem yourself, and the purpose of this course is to help you learn how to think about the complexity of solving problems on your own.
Furthermore, AI tools and the web will not be available during your exam (or during your job interviews), so you should learn to solve problems yourself, instead of relying on others to do your thinking for you.
As time runs out, students are sometimes tempted to get help from other students on assignments in a way that would violate the preceding policy on academic honesty. DO NOT DO THIS! If you do, I will refer the case to the Dean's Office, which is unpleasant for everyone. The assignments are worth very little, so it is not worth risking a sizable punishment. (Furthermore, I have noticed that the students who cheat on the homework assignments almost always fail the tests and exams, so even if I do not catch you cheating, you will likely fail the course if you do not do your own work on the homework assignments.)
It is important that you look at the senate
policy
on academic honesty and the faculty's academic integrity resources.
Announcements
- (Sep 22) I will be away to attend a conference Sep 26-Oct 3. You will write your test in class on Sep 29. I will be arranging an alternate activity in place of the October 1 class. I will not have office hours while I'm away, but I will answer questions by email, and I'm happy to set up a zoom meeting if you would like to talk to me while I'm away.
- (Sep 10) The department is holding a series of sessions to prepare students for the International Collegiate Programming Contest on Tuesdays from 15:00-17:00 in BRG 211. These contests are a great way to hone your programming skills, and they are also fun. For more information, contact Professor Allin.
- (Sep 4) The Fields Institute downtown is holding a celebration later this month for Mark Braverman, who won the prestigious Abacus Medal for contributions to theoretical computer science in 2022. This includes a public lecture on Sep 23 and a Student Night on Sep 24 for undergraduates. Follow the links to register for free tickets.
Important Dates
(Information will be added to this table thoughout the term.)
| First class | Wednesday, September 3 |
| Test 1 | Monday, September 29 |
| Reading Week (no classes) | October 13-17 |
| Test 2 | Wednesday, October 29 |
| Last date to drop course without receiving a grade | Tuesday, November 4 |
| Test 3 | Monday, November 24 |
| Last class | Monday, December 1 |
| Last date to withdraw from course (receiving W on transcript) | Tuesday, December 2 |
| Exam period | December 4-19 |
References
Course Textbook
[Sip] Michael Sipser.
Introduction to the Theory of Computation, 3rd edition.
Cengage Learning, 2013.
We will be focusing on Part III of the book.
The textbook website has lists of errata.
Cost: Can be purchased ($236) or rented ($78) from Cengage, or for about $225 at York Bookstore, or $162 at Amazon (as of Aug 21); used copies available at abebooks.com (but look for 3rd edition). A copy is on reserve at Steacie Library.
Other Books
-
[AB] Sanjeev Arora and Boaz Barak.
Complexity Theory: A Modern Approach.
Cambridge University Press, 2009.
A draft of the book is available online.
-
[BDG] José Luis Balcázar, Josep Diaz, Joaquim Gabarró.
Structural Complexity I, 2nd ed.
Springer, 1995.
Nicely written, accessible introduction. Available online at York Library via SpringerLink.
-
[BC] Daniel Pierre Bovet and Pierluigi Crescenzi.
Introduction to the Theory of Complexity.
Prentice Hall, 1994.
-
[DK] Ding-Zhu Du and Ker-I Ko.
The Theory of Computational Complexity, 2nd ed..
Wiley-Interscience, 2014.
-
[Gol] Oded Goldreich.
Computational Complexity: A Conceptual Perspective.
Cambridge University Press, 2008.
Preliminary versions of this book are available from the author's
website.
-
[HS] Steven Homer and Alan L. Selman.
Computability and Complexity Theory, 2nd ed..
Springer, 2014.
Available online at York Library via SpringerLink.
-
[Imm] Neil Immerman.
Descriptive Complexity.
Springer, 1999.
Emphasizes connections to formal logic.
-
[Pap] Christos Papadimitriou.
Computational Complexity.
Addison-Wesley, 1994.
Very nicely written book that covers a lot of ground.
Original Articles
-
[CR73] S.A. Cook and R.A. Reckhow. Time bounded random access machines, J. of Computer and System Sciences, volume 7, pages 354-375, 1973.
-
[HS65] J. Hartmanis and R.E. Stearns. On the computational complexity of algorithms, Trans. of the AMS, volume 117, pages 285-306, 1965.
Resources for Special Topics
-
[ACG] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela and M. Protasi.
Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties.
Springer, 1999.
Associated with this book is the online Compendium of NP Optimization Problems, which is like a version of Garey and Johnson's appendix (with more emphasis on approximations).
-
[CLRS] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.
Introduction to Algorithms, 3rd edition.
MIT Press, 2009.
Great general algorithms book, and it has a nice chapter on NP-completeness.
Available online at York Library.
-
[GJ] Michael R. Garey and David S. Johnson.
Computers and Intractability.
W. H. Freeman, 1979.
The bible of NP-completeness.
Johnson has also published a sequence of columns (available here) that form a kind of sequel to the book.
-
[GHR] Raymond Greenlaw, James Hoover, Walter L. Ruzzo.
Limits to Parallel Computation: P-completeness Theory.
Oxford University Press, 1995.
Available online from Ruzzo's web page.
-
[MM] Christopher Moore and Stephan Mertens.
The Nature of Computation
Oxford University Press, 2011.
Wide coverage of the theory of computation, with lots of good examples.
Available online via York Library (although you have to select the catalogue record for the printed copy to get access to its chapters).
-
[SP] Uwe Schöning and Randall Pruim.
Gems of Theoretical Computer Science.
Springer, 1995.
Each chapter presents a beautiful theorem from various fields of computer science (with a number from complexity theory).
Blogs
More advanced complexity resources
-
[Aar] Scott Aaronson (zookeeper).
The Complexity Zoo.
This wiki has information on hundreds of complexity classes.
Its bibliography
includes a huge number of papers on complexity theory.
-
[HO] Lane A. Hemaspaandra and Mitsunori Ogihara.
The Complexity Theory Companion.
Springer, 2002.
Arranges Theorems according to the techniques used to prove them.
-
[RW] Steven Rudich and Avi Wigderson, eds.
Computational Complexity Theory.
AMS and Institute for Advanced Study, 2004.
Lecture notes, starting from some basics, but moving quickly to more advanced topics.
-
[Wig] Avi Wigderson.
Math and Computation.
Unpublished manuscript, 2019.
Available from the author's web page.
-
[Zim] Marius Zimand.
Computational Complexity: A Quantitative Perspective.
Elsevier, 2004.
Focussed on questions of what fraction of problems in a class have certain properties.
Reading
This reading list may be adjusted somewhat during the term.
| Date | Section | Suggested Exercises |
| Sep 3 | Review chapter 0 and 3 | 0.1-0.8, 3.1-3.2, 3.7, 3.8, 3.10-3.13 |
| Sep 8 | 7.1, review 3.1, notes on RAM model | 7.1, 7.2, 3.8 |
| Sep 10 | review 3.2 | 3.12, 3.13 |
| Sep 10 | notes on Palindromes | Show every single-tape TM that decides {0x1y2x : x,y ≥ 0} takes Ω(n log n) steps |
| Sep 15 | 7.2 | 7.3-7.6, 7.8, 7.9, 7.13, 7.14, 7.15 |
| Sep 17 | 7.3 | 7.7, 7.12, 7.16 |
| Sep 24 | 7.4 | 7.18, 7.20-7.27 |
| Oct 6 | 7.5 | 7.17, 7.28, 7.30-7.33, 7.35, 7.38, 7.40-7.41 |
| Oct 20 | Optional: The Status of the P Versus NP Problem (from CACM, Sep 2009) and/or
P vs. NP survey results (from SIGACT News, Mar 2019; starts on p.4) | |
| Oct 27 | 10.1 | |
| Nov 3 | 8.0-8.1, 8.4 | 8.1, 8.4, 8.7, 8.9, 8.17, 8.20, 8.22 |
| Nov 5 | 8.5, 8.6 | 8.25,8.29,8.32 |
| Nov 12 | 8.2, 8.3 | 8.3,8.4,8.6,8.11,8.15 |
| Nov 17 | 9.1 (to page 371) | 9.1-9.3,9.12,9.13 |
| Nov 26 | p.396-398, Defn 10.10 | 10.7, 10.11, 10.19, 10.20, 10.22 |
NOTE: Exercise numbers are from the third edition of the textbook.
Course Handouts
Updated October 3, 2025