Tik-79.240 Special Course on Computational Complexity
Program Autumn 2001
(Home assignments from Papadimitriou's book).
- 12.9.2001
- Introduction (IN)
Chapter 2: Basics of Turing machines (IN)
Home assignments: 1.4.10 (b),(c),(d),(g) and 2.8.8 (a)
- 19.9.2001
- No lectures
- 26.9.2001
- Chapter 2 & 3: More on Turing machines, time and space complexity,
undecidability (IN)
Home assignments: 2.8.18 (a) and 3.4.1 (b), (c) and (g)
- 3.10.2001
-
- Chapter 4 & 7: Boolean logic; relations between complexity
classes (IN)
Home assignments: 4.4.5 and 7.4.5
- 10.10.2001
-
- Chapter 8: Reductions and completeness (IN)
Home assignments: 8.4.2 and 8.4.3
- 17.10.2001 (Seminar talks start)
- Chapter 9: NP-complete problems
pp. 181-188, Korhonen
pp. 188-193, Falck
pp. 193-199, Honkela (Slides: [PS])
Home assignments: 9.5.2 and 9.5.6
- 24.10.2001
-
pp. 199-206, Koskela (Slides: [PS])
Chapter 10: coNP and function problems
pp. 219-227, Lilja
pp. 227-234, Saikkonen (Slides: [PS])
Home assignments: 9.5.7 and 9.5.10 (a)
- 31.10.2001
- Chapter 11: Randomized computation
pp. 241-248, IN (Slides: [PS])
pp. 248-256, Peltonen
pp. 256-263, Virtanen (Slides: [PS])
Home assignments: 10.4.13 and 10.4.19 (a)
- 7.11.2001
-
pp. 263-271, Aalto (Slides: [PS])
Chapter 12: Cryptography
pp. 279-287, Järvisalo (Slides: [PS])
pp. 287-293, Oikarinen (Slides: [PS])
Home assignments: 11.5.14 and 11.5.16 (a)
- 14.11.2001
-
Chapter 13: Approximability
pp. 299-307, Särelä (Slides: [PDF.gz]
[PS.pz/4up])
pp. 307-315, Petäjä (Slides: [PS])
pp. 315-322, IN (Slides: [PS])
Home assignments: 12.3.9 (b) and 13.4.13 (a)
- 21.11.2001
- Chapters 14-16 (IN)
Home assignments: 14.5.5 (only the KNAPSACK part) and 15.5.9 (a)
- 28.11.2001
- Chapter 17: The Polynomial Hierarchy
pp. 411-418, Mäki (Slides: [PS]
[PDF])
pp. 418-424, Degtyarenko
pp. 424-432, Stepanek
Home assignments: 17.3.2 (a), (b) and 17.3.12
- 4.12.2001, 16-18, TB353
- Chapter 18: Computation that Counts
pp. 439-447, Ruusu (Slides: [PS])
pp. 447-451, IN (Slides: [PS])
Chapter 19: Polynomial Space (IN)
Home assignments: 18.3.6 and 19.4.5
- 5.12.2001
-
Chapter 20: A glimpse beyond (IN)
Course summary and feedback session
Home assignments: 9.5.18 (a), (b) and 9.5.34 (a)