COSC6115, Winter 2009

Computational Complexity
Winter 2009

Instructor: Eric Ruppert
Office: Computer Science Building, room 3042
Email: [my last name]
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: Tuesdays and Thursdays from 10:00 to 11:30 in room 325 of Bethune College.
Office Hours: Tuesdays and Fridays 13:00-14: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 "[6115]". Send messages in plain text, without attachments.


Course Overview

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 (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.

Much of the material will be taught from first principles, so there are no specific prerequisites. However, some background in algorithms and theoretical models of computing (e.g. Turing machines, finite automata) would be helpful, and you should be comfortable reading and writing mathematical proofs.

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

Marking scheme

Homework exercises 80%
Class presentation 20%




Original Articles

Resources for Special Topics

More advanced complexity resources

Course Handouts

Updated May 15, 2009