CSC363 - Computational Complexity and Computability (Spring 2005)

Instructor: Paul McCabe
E-mail: pmccabe [at] cs [dot] utoronto [dot] ca

If you wish to meet outside of regular office hours, please send me an email to arrange a time and place. As I share an office with others, drop-ins are not possible.

[Syllabus] [Lecture Outline] [Tutorials] [Announcements] [Assignments] [Grades]

Timetable

Lectures: Tuesdays and Thursdays, 10:00 am, SS2135
Tutorials: Fridays, 10:00 am
Instructor's Office Hours: Mondays, 3:30 - 4:30 pm, BA3201

Textbook and recommended reading

M. Sipser. "Introduction to the Theory of Computation". PWS Publishing Company, 1997.

Here is a link to the paper "PRIMES is in P" by Agrawal, Saxena, and Kayal. This is purely for your own interest, and is probably fairly difficult to understand, but there it is.

Here is a link to Stephen Cook's 1971 paper "The complexity of theorem proving procedures", where he proved that SAT is NP-complete. The relevant part is "Theorem 1". Note that the type of reduction used in the paper is different than the one we used in class: in the paper, a language A is reducible to B if you can use a polytime solver for B to decide A in polynomial time (possibly making several calls to the B-solver).

M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. (1979) This book is an excellent reference, and contains a large compendium of NP-complete problems in the back.

Grading scheme

In order to pass this course, you must achieve a grade of at least 40% on the final exam.

Lateness policy

Assignments submitted after 6 pm on the thursday following the due date will not be accepted. The lateness penalty will be applied to each question individually; a solution submitted on time will be marked normally even if other solutions are late.

Due dates

Links