CAS 705: Computability and Complexity
Fall 2006
- Instructor: Michael Soltys, email:
my last name at mcmaster.ca
- Course Information
- Lectures: M,W,F 9:30-10:20, in ITB-222.
- Course outline:
The relationship between problems, algorithms, and languages.
Computability: finite automata, rewriting systems, Turing machines
(linear speedup, robustness, and the Universal Turing machine).
Recursive functions and Cobham's Theorem. Determinism and
non-determinism. Recursive and recursively enumerable languages. The
Halting problem and the diagonalization technique. Church-Turing
thesis, and Rice's theorem. Complexity: classes defined in terms of
time, space, and circuits. Uniformity. 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. NP and co-NP, propositional proof systems, and Horn
clauses. Kolmogorov complexity, and the Shannon principle.
- Textbook:
Computational Complexity, by
Christos H. Papadimitriou , and here is the
errata , and the book cover:
- Check this web page regularly for announcements.
-
Previous versions of this course:
2005,
2004,
2003.
This course was also taught in 2002 as
cas776 -- Fall 2002.
- Please Read:
McMaster Academic Integrity Statement.
Announcements:
- Dec 7: The exam has been marked, and the final grades
submitted. We celebrated accordingly at the Phoenix:
Picture 1 and
Picture 2.
- Nov 20: Assignment 5 due date has been extended to Monday
November 27.
- Nov 17: Ryan Lortie suggested that it would be good to keep
going with complexity next term. In light of this great idea, I would
like to propose an informal Complexity Theory Seminar Series.
If you would be interested in attending, send me an email, and I will
add you to the mailing list. If there is sufficient interest, we can
start meeting next term, once a week for an hour. It would be good to
decide a time slot soon, so that I can reserve a room with Cathie. If
there is a volunteer who would like to set up a web page for those
seminars (the web page would contain seminar announcements and such),
and a mailing list, that would be most welcome! As far as the
seminars are concerned, the idea is that we (i.e., the participants)
would take turns giving presentations on topics in complexity,
continuing with results which we did not have time to present during
the course (e.g., cryptography, descriptive complexity, Kolmogorov
complexity, average complexity, etc., etc.). It would be a good
opportunity to learn to give talks, and to discover research problems.
- Nov 15: Solutions to Assignment 4 have been posted below.
- Nov 10: Assignment 5 has been posted below.
- Nov 8: On Monday Nov 13 there will be coffee and cookies in
class, to kick off Greg's three lectures on L=SL.
- Nov 7: I have posted below a hint for Q5(b) on A4.
- Nov 4: Click here for the
slides on the lower bound for resolution. Note that following Greg
Herman's observations, the Lemma on page 5 has been slightly restated:
we are showing the existence of large clauses directly on the
monotone side.
- Nov 4: For Q3 on A4, Dai Tri Man Le points out that C is not
formally defined when both alpha and beta are unsatisfiable. The
reason is that it does not matter how you define it in that case; say
you define it to be 0.
- Nov 3: I have booked ITB-225 for the final exam, for
Wednesday December 6, 10:30-1:30. Please let me know if this is
not good, but keep in mind that it is very difficult to get a free
room for three hours during the last week of classes!
- Oct 30: Solutions to A3 have been posted below.
- Oct 27: Assignment 4 has been posted below.
- Oct 23: Note the correction on the last line of the first page
of assignment 3 (it is highlighted in yellow).
- Oct 22: You may find the Complexity Zoo
useful.
- Oct 21: Dai Tri Man Le pointed out that in Q2b on Assignment 3,
the definition of \Sigma_i^{Alt} should say that these are
polytime alternating Turing machines. Also, define the zero
level to by just P, for all three models.
- Oct 20: Assignment 2 solutions have
been posted below.
- Oct 17: Ryan Lortie pointed out that in assignment 3, question
2b, the definition of alternating Turing machines is incomplete.
Please click here for assignment 3 with 2b
corrected.
- Oct 14: Hao Xia pointed out that the top paragraph on the
second page of Assignment 2 requires some
ellaboration. In particular, how do we know that if each gate has a
probability of error of at most epsilon/s, then the entire circuit,
which has s gates, has probability of error at most epsilon? To see
this we cannot just multiply the probabilities, as they are not
necessarily independent. However, we can use Boole's inequality,
which is a consequence of the important Inclusion-Exclusion
Principle, and which states that Pr[A1 U A2 U ... U An] <=
Pr[A1]+Pr[A2]+...+Pr[An]. Click here to read a
note by Hao Xia regarding the I-E principle.
- Oct 13: Hao Xia pointed out that there is a typo on slide 12 of
the parity slides (corrected).
In the middle the top part of the binomial should not be n (as
in the original), but rather 4kln(n).
- Oct 13: Assignment 3 has been posted below. Click here for the slides on the
Immerman-Szelepcsenyi Theorem.
- Oct 10: Writing up the solutions to A2, I discovered two typos
in Q9: in the second line, the q should be script q, and in the middle
of the paragraph I define the function f:A-->R. This should actually
be f:S-->R. If you click on the original A2
below, the two typos are highlighted in yellow.
- Oct 4: Click here for the
PARITY not in AC0 slides (with a small correction on slide 10 added
in the evening).
- Oct 4: Who is
Chavy Chase?, and he is not to be confused with
Chebyshev, Pafnuty Lvovich, who gave us the inequality.
- Oct 4: Solutions to assignment 1 have been posted below.
- Oct 4: A Theoretical Computer Science
Cheat Sheet
- Sept 30: The following is an interesting papers on the main
problem of complexity theory: P vs NP. It is not required
reading, but it is non-technical and it gives a nice context to our
course.
- Sept 30: Assignment 2 has been posted below.
- Sept 14: The first assignment has been posted below.
- The first two lectures, Friday September 8, and Monday September
11, will be taught by Greg Herman.
Assignments and Tests:
