CAS 705: Computability and Complexity
Fall 2009
- Instructor: Michael Soltys, email:
my last name at mcmaster.ca
- Course Outline
- Lectures: Tu, Th, Fr, 11:30-12:20, in
ITB-222.
- Course outline:
Complexity classes defined in terms of time, space, and circuits. The
reachability method (Savitch's theorem, and the Immerman-Szelepscenyi
theorem). The P versus NP problem (and Cook's Theorem), reductions
and completeness. The Time and Space Hierarchy Theorems. Randomized
and parallel computations. Cryptography: Rabin-Miller primality
testing, Diffie-Hellman, ElGamal, and RSA protocols; Elliptic curve
cryptography; Lattice-based cryptography
- Textbook:
An introduction to computational complexity, by Michael Soltys,
published by Jagiellonian University Press, 2009.
See a sample of the
book.
- Check this web page regularly for announcements.
-
Previous versions of this course:
2008,
2006,
2005,
2004,
2003.
This course was also taught in 2002 as
cas776 -- Fall 2002.
- Please Read:
McMaster Academic Integrity Statement.
Announcements:
- Dec 14: Solutions to final exam (by Xiao Shu) have been posted
below.
- Dec 5: Solutions to assignment 4 (by Jason Jaskolka) have been
posted below.
- Nov 17: The take home final exam has been posted below.
- Nov 11: The last assignment, number 4, has been posted below
(it is due on November 24).
- Nov 4: For question 1 in assignment 3, use the counting idea in
the Immerman-Szelepcsenyi theorem. On an input x, to establish
whether x is in the complement of L, compute first k=f(|x|), i.e., k
is the number of strings of length |x| in L. Now use this information
to provide a non-deterministic algorithm that checks whether x is not
in L (in order to check that it is in the complement of L). This
algorithm should simulate M (where L=L(M)) on every string y of length
|x|, keeping track of how many of these y's are accepted...
- Oct 27: Solutions to assignment 2 have been posted below-- very
elegand solutions due to Xiao Shu.
- Oct 26: Assignment 3 has been posted below.
- Oct 10: Solutions to assignment 1 (due to Xiao Shu) have been
posted below. Assignment 2 has been posted below; it is due on
October 23.
- Oct 1: Two documents that you might find useful during this
course:
- Sept 19: The first assignment (due October 6) has been posted
below.
- Sept 12: There will be no lecture on Tuesday September 15.
Assignments and Exam: