CSC2401 Home Page (Fall 2008)
This page will provide WWW access to various documents concerning CSC2401.
Announcements will also be made on
Announcements for week of November 24.
There is no distinguished lecture this week but there is a "grad
skills seminar at 11 on Tuesday. We will therefore meet Tuesday 10-11 and
then again Wed 12-1.
This week we will finish discussing basic properties of
and examples of languages in the poly time randomized complexity classes.
Periklis will start the discussion of IP and ZKIP.
There are now 3 questions on the final problem set
and there may be one more. There was a typo in question 2 that has
now been corrected. Namely, the question calls for a proof
that there is a language L in EXPSPACE that is not in SIZE(M(n)-1)
whereas it previously and erronously said that L was not in SIZE(M(n)).
Please send any comments or questions to the instructor:
This course is a standard graduate level introduction
to complexity. The course will be related to previous versions
of this course but this year the course will
be more of a foundational course in the sense that we
will be focusing somewhat more on the classical results in the field
with less emphasis on more current research activity.
The text is ``Introduction to the Theory of Computation: Second Edition'' by
Michael Sipser. A supplemental text is ``Theory of Computation''
by Dexter Kozen.
There are a number of other text books in this area.
One excellent advanced text that has just been published
Oded Goldrich's Computational Complexity . Another soon to
be published excellent advanced text is
Sanjeev Arora and Boaz Barak's Complexity Theory:A Modern Approach.
A draft of this text is available on thei web site.
Although the course will be somewhat different,
in many regards the
the course will be similar to the versions taught in 2001,
2003, 2005 and 2007.
Problem Sets, Tests and Other Handouts will be posted here.
Problem set 1 in pdf format
Problem set 2 in pdf format
Problem set 3 in pdf format