CSE6115, Fall 2012

Computational Complexity
Fall 2012

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: Wednesdays and Fridays from 10:30 to 12:00 in room 103 of Founders College.
Office Hours: I will hold regular office hours on Mondays from 12:00 to 1:00 and Wednesdays from 16:00 to 17: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:

You can look at the 6115 course web page from the last time it was offered to get an idea of what was covered then.

Marking scheme:
Homework exercises 60%
Class presentation10%
Paper report10%
Paper presentation 20%

Most of the homework exercises will require you to write a proof. For the class presentation, you will have to read about some complexity class and report your findings (the definition of the class, why it is important, maybe one or two basic facts about it) to the class. For the paper presentation, you will be required to read a research paper on complexity theory and present the results to the class. More details about all of this work will be given in class.




Original Articles

Resources for Special Topics

More advanced complexity resources

Course Handouts

Updated November 23, 2012