T79.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: NPcomplete problems (IN)
 23.10.2003

Chapter 9: NPcomplete problems  cont'd (IN)
Chapter 10: coNP and function problems (IN)
 30.10.2003
 Chapter 11: Randomized computation (Seminar talks begin)
pp. 241248, Patrikainen
pp. 248256,
pp. 256263,
 6.11.2003

pp. 263271,
Chapter 12: Cryptography
pp. 279287, Aho
pp. 287293, Anderson
 13.11.2003

Chapter 13: Approximability
pp. 299307, Salmela
pp. 307315, Kokkonen
pp. 315322, Juhala
 20.11.2003
 Chapters 1416: On P vs. NP; Parallel Computation; Log Space (IN)
 27.11.2003
 Chapter 17: The Polynomial Hierarchy
pp. 411418, Virtanen
pp. 418424,
pp. 424432,
 2.12.2003
 Chapter 18: Computation that Counts
pp. 439447, Aatrokoski
pp. 447451,
Chapter 19: Polynomial Space (IN)
 4.12.2003

Chapter 20: A Glimpse Beyond (IN)
Course summary and feedback session