CAS 705: Computability and Complexity
Fall 2005
- Instructor: Michael Soltys, email:
my last name at mcmaster.ca
- Course Information
- Lectures: Mondays 2:30-3:20, Wednesdays
9:30-10:20, Fridays 10:30-11: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:
We may supplement it with the more advanced (not required, but
recommended)
Gems of Theoretical Computer Science, by U. Schöning and R.
Pruim
- Check this web page regularly for announcements.
-
Previous versions of this course:
2004 and
2003.
This course was also taught in 2002 as
cas776 -- Fall 2002.
- Please Read:
McMaster Academic Integrity Statement.
Announcements:
- Dec 8: Solutions to Assignment 6 have been posted below.
- Dec 6: The exam has been posted below.
- Nov 29: Click here for a hint on how
to do question 1d) on assignment 6.
- Oct 25: Click here for the
slides on diagonalization. (And here
is the PostScript version.)
- Oct 19: Two clarifications:
- Recall R^k, the regular expressions with the exponentiation
operator. The language that is EXPSPACE-complete is the language of
pairs of such expressions that generate the same language. That is,
(R,S), where R,S are regular expressions with exponentiation, and
L(R)=L(S).
- Recall that a tree resolution refutation of minimal size is
regular. The corresponding result for dag-like resolution fails.
Andreas Goerdt showed that there is an infinite sequence of
contradictory sets of clauses having polysize dag-like resolution
refutations, for which the size of any regular resolution refutation
grows faster than any fixed polynomial.
- Oct 18: Hint for doing question 4 on assignment 3: You have to
show that NC^1=BF. Show containment in both directions. Note that
showing that NC^1 is in BF is easy; there is only one difficulty: a
boolean formula is a circuit where each gate, except input gates, is
used only once as the input to another gate. In NC^1 circuits,
outputs can be re-used, so you have to replicate subcircuits to
convert the whole circuit into a boolean formula. But how much does
this increase the size? For the other direction, note that a
brute-force translation of a boolean formula into the corresponding
circuit does not work, as the boolean formula can be of the form
(av(av(av(av(av(av(ava))))))), so the depth of this would not be
"logarithmic". But, we can "rebalance" the formula, and give it as
(((ava)v(ava))v((ava)v(ava))). Showing how to do this rebalancing in
general is the hard part of this question.
- Oct 16: Click here for the
slides on resolution.
- Oct 3: Assignment 3 has been posted below.
- Oct 3: For question 3 on Assignment 2, you assume that the
circuit takes 2n inputs (two n-bit binary numbers), and n+1 outputs
(the result of their addition). For the second part (repeated
addition), you have to give a circuit that computes the sum of n,
n-bit integers (so it takes n-squared many inputs; how many outputs?).
Here is a hint for repeated addition: you can convert the sum of 3
n-bit integers into the sum of 2 n-bit integers, where one of the new
integers is the naive sum without carry, and the other is the
carry.
- Oct 3: Monday October 10th is Thanksgiving, so there will be no
class; you can hand in assignment 2 on Friday (October 7th), or
Wednesday October 12th.
- Sept 29: Solutions to Assignment 1 have been posted below.
- Sept 26: Click here for the
slides on the parity not in AC^0 result.
- Sept 26: Final Exam: December 5th,
12:30-3:30, in ITB-222
- Sept 23: Assignment 2 has been posted below. Assignment 1 is
due at the beginning of Monday's lecture.
- Sept 21: We should schedule the final exam at the next lecture.
Please think about the times convenient for you; I am partial to doing
it as early as possible.
- Sept 10: The first assignment (due on Sept 26 at the beginning
of the lecture) has been posted below.
- First meeting on Friday Sept 9, at 10:30 in ITB-222.
Assignments and Tests: