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

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: