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

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: