Complexity Theory, Spring 1999

Course Description

PostScript file.

Lecturers

Peter Bro Miltersen and Søren Riis.

Time and Place

Tuesdays, 12.15-14.00 in koll.B3, and Fridays, 13.15-15.00 in koll.B3, starting February 2nd and continuing for 7 weeks.

Text

C. Papadimitriou: Computational Complexity, Addison-Wesley 1994.

Homeworks

In general, a homework will be assigned to you each Friday (sometimes, you may get it already Tuesday). It will also appear on this web page. A solution should, unless otherwise mentioned, be handed in the following Friday. You are encouraged to discuss the homeworks with each other, but such discussions should be mentioned in your solutions. You are also encouraged to come see the lecturer about the homework. Each homework will contain a "challenge"-problem which is not marked. Your solution to the other problems will be marked. The marks will make up your final grade.

First homework, hand in Friday, February 12.

Second homework, hand in Friday, February 19.

Third homework, hand in Friday, February 26.

Fourth homework, hand in Friday, March 5.

Fifth homework, hand in Friday, March 26.

Lectures given

February 2nd (PBM): One-tape and multi-tape Turing machines. Simulating a multi-tape Turing machine on a single-tape one. The speed-up theorem.

February 5th (PBM): The time hierarchy theorem. The gap theorem (mentioned). Boolean circuit complexity. Nondeterministic machines.

At the lecture, I mentioned that proofs(?) of NP=P are quite common. Here is a link to a published (and unretracted) one, in a serious(?) journal, the Southwest journal of pure and applied mathematics: Polynomial-Time Partition of a Graph into Cliques by Anatoly Plotnikov. And here is a page discussing this proof.

February 9th (PBM): Space bounded machines. Savitch' theorem. Logspace reductions. Completeness.

February 12th (PBM): Immerman/Szelepscenyi's theorem. Cook's theorem. NP-complete problems.

February 16th (PBM): Feedback on Homework 1 ("gap"-theorem for single tape machines proved). More NP-complete problems.

February 19th (PBM): Alternating machines. Parallel computation thesis. QBF PSPACE-complete. The polynomial hierarchy, Alternating machines with random access to the input.

February 23th (SR): Proof complexity in Propositional logic, Cook's and Reckhows result, Tseitin's tautologies and expander graphs.

Febrary 26th (SR): Second Order Logic, Ehrenfeught-Frasse games, Horn formulas. Characterisation of NP, co-NP and P in terms of finite model theory.

March 2nd (SR): NP vs. co-NP, and NP vs P in terms of Ehrenfeught-Frasse games.

March 3rd (!!) (SR): Complexity of various mathematical theories and decision procedures.

March 9th (PBM): More PSPACE-complete problems. Alternating machines with random access to input and the fine structure of P.

March 12th.(PBM): The polynomial hierarchy. Relativized computation. Karp and Lipton's theorem.

March 16th (PBM): Fortnow's lower bound for the time-space tradeoff of SAT. Randomized complexity classes. Adleman's theorem. Sipser and Lauteman's theorem (mentioned).

March 23th (PBM): Hastad's switching lemma and its application to lower bounds for constant depth circuits.