CSE4115, Fall 2012
CSE4115
Computational Complexity
Fall 2012
Web page contents:
General Information
Announcements
Important Dates
Resources
Reading
Course Handouts
General Information
Instructor: Eric Ruppert
Office: Lassonde (Computer Science) Building, room 3042
Email: [my last name] @cse.yorku.ca
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: Mondays and Wednesdays from 14:30 to 16:00 in room 122 of the Chemistry building.
Office Hours: I will hold regular office hours on Mondays from 12:00 to 1:00 and Wednesdays from 4:00 to 5:00. If you cannot make it at those times, feel free to contact me to make an appointment at a different time. You can also try dropping by my office.
The best way to contact me is probably by email. Please use your cs account when sending me email, and start your subject line with "[4115]". Send messages in plain text, without attachments.
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
| Homework exercises | 30% |
| Midterm test | 20% |
| Class presentation | 10% |
| Classroom participation | 10% |
| Final exam | 30% |
Academic Honesty
It is important that you look at the departmental
guidelines
on academic honesty.
Although you may discuss the general approach to solving a problem
on a homework assignment 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 look at the course textbook and your own
lecture notes but no other outside sources.
If you get stuck while working on one of the assignments, I encourage
you to come to my office hours to get help with it.
Announcements
- (Nov 6) The bonus quiz on Friday, November 9 will be at 2pm in TEL 0008.
- (Oct 1) The midterm test will be on October 24.
- (Sep 18) To submit your solution to part (a) of Assignment 1, use the command "submit 4115 a1 file", where file contains your answer.
- (Sep 18) Assignment 2 was posted yesterday.
Important Dates
(Information will be added to this table thoughout the term.)
| First class | September 5 |
| Thanksgiving (no lecture) | October 8 |
| Midterm test | October 24 |
| Hallowe'en (no lecture) | October 31 |
| Drop deadline | November 9 |
| Last class | December 3 |
| Exam period | December 5-21 |
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.
If you have the 2nd edition, that's fine (there are not very many differences between the two editions).
The textbook website has lists of errata.
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.
-
[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.
Wiley-Interscience, 2000.
-
[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.
Springer, 2001.
-
[HU79] John E. Hopcroft and Jeffrey D. Ullman.
Introduction to Automata Theory, Languages and Computation, 1st ed.
Addison-Wesley, 1979.
-
[Imm] Neil Immerman.
Descriptive Complexity.
Springer, 1999.
Emphasizes connections to formal logic.
-
[Pap] Christos Papadimitriou.
Computational Complexity.
Addison-Wesley, 1994.
-
[Sav] John E. Savage.
Models of Computation: Exploring the Power of Computing.
Addison-Wesley, 1998.
Part III of this book discusses complexity theory.
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.
-
[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.
(See their web site.)
-
[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).
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.
-
[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
| Date | Section | Suggested Exercises |
| Sep 5 | Review chapter 0 and 3 | 0.1-0.8, 3.1-3.2, 3.7, 3.8, 3.10-3.13 |
| Sep 10 | 7.1, review 3.1 | 7.1, 7.2, 3.8 |
| Sep 12 | notes supplied | Show every single-tape TM that decides {0x1y2x : x,y ≥ 0} takes Ω(n log n) steps |
| Sep 17 | review 3.2, supplementary reading: Sec 2.6 of [Pap] | 3.12, 3.13 |
| Sep 19 | 7.2 | 7.3-7.6, 7.8, 7.9, 7.13, 7.14, 7.15 |
| Sep 24 | 7.3 | 7.7, 7.12, 7.16 |
| Sep 26 | 7.4 | 7.18, 7.20-7.27 |
| Oct 1-22 | 7.5 and package of NP-completeness results handed out | 7.17, 7.28, 7.30-7.33, 7.35, 7.38, 7.40-7.41 |
| Oct 29 | 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 14 | 9.1 | 9.1-9.3,9.12,9.13 |
| Nov 19 | 9.3,10.5 | |
| Nov 21 | 8.2 | |
NOTE: Exercise numbers are from the third edition of the textbook.
Course Handouts
Updated November 23, 2012