CAS 705: Computability and Complexity
Fall 2009
 Instructor: Michael Soltys, email:
my last name at mcmaster.ca
 Course Outline
 Lectures: Tu, Th, Fr, 11:3012:20, in
ITB222.
 Course outline:
Complexity classes defined in terms of time, space, and circuits. The
reachability method (Savitch's theorem, and the ImmermanSzelepscenyi
theorem). The P versus NP problem (and Cook's Theorem), reductions
and completeness. The Time and Space Hierarchy Theorems. Randomized
and parallel computations. Cryptography: RabinMiller primality
testing, DiffieHellman, ElGamal, and RSA protocols; Elliptic curve
cryptography; Latticebased 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 ImmermanSzelepcsenyi 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 nondeterministic 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: