T-79.240 Special Course on Computational Complexity

Lecture/seminar talk schedule (Autumn 2003)


(Corresponding tutorials on the following Tuesday; home assignments from Papadimitriou's book).
11.9.2003
Introduction (IN)
Chapter 2: Basics of Turing machines (IN)
18.9.2003
Chapter 2 & 3: More on Turing machines, time and space complexity, undecidability (IN)
25.9.2003
No lectures (and therefore no tutorial on Tue 30.9.2003)
2.10.2003
Chapter 4 & 7: Boolean logic; relations between complexity classes (IN)
9.10.2003
Chapter 8: Reductions and completeness (IN)
16.10.2003
Chapter 9: NP-complete problems (IN)
23.10.2003
Chapter 9: NP-complete problems - cont'd (IN)
Chapter 10: coNP and function problems (IN)
30.10.2003
Chapter 11: Randomized computation (Seminar talks begin)
pp. 241-248, Patrikainen
pp. 248-256,
pp. 256-263,
6.11.2003
pp. 263-271,
Chapter 12: Cryptography
pp. 279-287, Aho
pp. 287-293, Anderson
13.11.2003
Chapter 13: Approximability
pp. 299-307, Salmela
pp. 307-315, Kokkonen
pp. 315-322, Juhala
20.11.2003
Chapters 14-16: On P vs. NP; Parallel Computation; Log Space (IN)
27.11.2003
Chapter 17: The Polynomial Hierarchy
pp. 411-418, Virtanen
pp. 418-424,
pp. 424-432,
2.12.2003
Chapter 18: Computation that Counts
pp. 439-447, Aatrokoski
pp. 447-451,
Chapter 19: Polynomial Space (IN)
4.12.2003
Chapter 20: A Glimpse Beyond (IN)
Course summary and feedback session