CS 464/664 -- Computational Complexity

Winter 2002



Assignment 1

Assignment 2

Assignment 3

Assignment 4


Assignment 1 solution

Assignment 2 solution

Assignment 3 solution

Assignment 4 solution


Troy Vasiga, DC 3103, x6937, tmjvasig@math.uwaterloo.ca
Office hours: W 3:30-4:30 or by appointment

Please feel free to drop by with course questions or just to chat. You can often find me in at other times; email to make sure.

Teaching Assistant

Keith Ellul, DC2130, x3333, kbellul@hopper. Office hours: Th 2-3


Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.

There is also a page for errata that you should read in order to update your copy of the text. In fact, you should also look at this errata, since it has quite a few errors which are not in the original.

Background required

You should have seen Turing machines and their variants as a model for studying computation. You should know the basics of undecidability, time complexity and NP-completeness. At Waterloo, CS 360 and CS 341 cover these topics quite adequately. See me if you feel unsure about your background.

Course description

What resources do computations use? How much of a given resource does a problem really require? How can we characterize problems that need certain resources? These and similar questions form the starting point for the course.

We shall consider the basic resources of time and space (memory), as well as less-quantifiable resources such as nondeterminism, randomization, interaction and parallelism. For each, we shall identify ``complete'' problems that characterize the use of the resource or investigate why no such problems exist.

The various resources have close connections to one another, singly and in combination. Along with showing the known connections, we shall discuss why some relationships remain unknown. In particular, we shall look at some recent approaches to the P=?NP question.

About the text

We will cover the material in a fairly ordered sequence, staying close to the order of the text.

Each chapter ends with a collection of ``Notes, References and Problems.'' Some of them merely amuse, but others point to additional insights and results. I shall take some of the lecture material from these sections.

Course outline

Consider this a rough guide only. I will give more detail and specific readings as the course progresses.
Basics and review (1 week):
Turing machines: definitions and notation. Time and space complexity. Linear speedup. (Ch. 2.)
Undecidability and Logic (1 week)
UTM, halting, recursive, recursively enumerable, recursively separable. (Chs. 3 and 4)
First and Second order logic (1 week)
Godel's completeness theorem. (Ch. 5)
Number theory and complexity (1 week):
Godel's incompleteness theorem. (Ch. 6)
Complexity classes and completeness (1 1/2 weeks):
Equivalence and separation of classes. Reductions and completeness for general classes. (Chs. 7 and 8.)
Nondeterminism (2 weeks).
A variety of NP-complete problems. Complementary problems. (Chs. 9 and 10.)
Randomization, interaction, and approximation (2 weeks):
Randomization as a computational resource (Ch. 11). Its use in two-party computations (Ch. 12). Two-party computations and (non)approximability of NP-complete problems (Ch. 13).
Parallel computation (2 weeks):
Very fast parallel computation. Parallel models: PRAMs, circuits, and alternation. (Chs. 15 and 16.)
Beyond NP: polynomial space (1 week):
Relations of polynomial space bounds to time, parallelism and interaction. (Ch. 19.)

Course work

The written work for CS 464 will comprise homework assignments and a take-home final exam.

Homework assignments:

There will be four homework assignments, which I expect to be due in class on Fridays: January 28, February 15, March 8, and March 29. Sixty percent of the course grade will be based on these assigned problems.

You must do your own work on the assigned problems. You are permitted to discuss general aspects of the assigned problems with other students in the class, but you must create your own solution based on your own understanding of the material. Normally, a discussion in which one of the participants writes something down for the other prevents doing one's own work. You are of course free to discuss the problem with the instructor or the TA.

Along with the assigned problems, I will suggest some non-credit study problems. The problems will vary in difficulty from very easy to very hard; some may involve library readings. I intend that you will use these problems to practice the material and to deepen your understanding. You are free to use these non-credit problems as you see fit: solve them yourself, discuss them with friends, ask questions of me or the TA, etc.


The final examination will be a take-home; you will choose a period of several days within the normal exam period in which to write it. The take-home exam will require understanding and interpretation which is deeper than the assignments. The take-home exam is 40% of the course grade.

Students taking CS 664:

Students taking this course as CS 664 will complete a written project which will be worth 20%. Assignments and the take-home final will be worth 40% each.

Due Dates (tentative)

Assignments due in class on the given day.

Friday, January 28 Assignment 1
Friday, February 15 Assignment 2
Friday, March 8 Assignment 3
Friday, March 29 Assignment 4
TBA Final Exam