COSC6115, Winter 2001

COSC6115W: Computational Complexity
Winter 2001

General Information

Instructor: Eric Ruppert
Office: CCB 344
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: MWF14:30 in Bethune College, room 228
Office Hours: After lectures, or by appointment


This course is intended to give graduate students a solid grasp of 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 (eg. 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 (eg. 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.

The exact set of topics to be covered will depend partly on students' interests and background, but here is a tentative list of topics:

Most of the material will be selected from the textbook, listed below, which is well-written and provides an excellent introduction to the subject.

Important Dates

Monday, February 26First day of winter term classes
Wednesday, March 21Assignment 1 due
Monday, March 26 No class
Monday, April 9 Assignment 2 due
Friday, April 13 Good Friday (no class)
Monday, April 30 Assignment 3 due
Friday, May 11 Last day of winter term classes
Friday, May 18 Assignment 4 due


Textbook A list of the sections covered so far is here.

Other References

See my page of links for web pages related to theoretical computer science.

Course Handouts

To view a course handout, select one of the following links. Most of the documents are in PostScript format. (If you don't have a PostScript viewer, you can obtain one from here.)

Updated May 2, 2001