T-79.240 Special Course on Computational Complexity
Lecture/seminar talk schedule (Autumn 2004)
- Lecture 1 (14.9.2004)
- Introduction (IN)
Chapter 2: Basics of Turing machines (IN)
- Lecture 2 (21.9.2004)
- Chapter 2 & 3: More on Turing machines, time and space complexity,
undecidability (IN)
- Lecture 3 (28.9.2004)
- Chapter 4 & 7: Boolean logic; relations between complexity
classes (IN)
- Lecture 4 (5.10.2004)
-
- Chapter 8: Reductions and completeness (IN)
- Lecture 5 (12.10.2004)
- Chapter 9: NP-complete problems (IN)
- Lecture 6 (19.10.2004)
-
Chapter 9: NP-complete problems - cont'd (IN)
Chapter 10: coNP and function problems (IN)
- Lecture 7 (26.10.2004)
- Chapter 11: Randomized computation (Seminar talks begin)
pp. 241-248, Pottonen
pp. 248-256, Hirsimäki
pp. 256-263, Ukkonen
- Lecture 8 (2.11.2004)
-
pp. 263-271, Käsper
Chapter 12: Cryptography
pp. 279-287, Tikanmäki
pp. 287-293, Rusanen
- Lecture 9 (9.11.2004)
-
Chapter 13: Approximability
pp. 299-307, Nikander
pp. 307-315, Karelahti
pp. 315-322, IN
- Lecture 10 (16.11.2004)
- Chapters 14-16: On P vs. NP; Parallel Computation; Log Space (IN)
- Lecture 11 (23.11.2004)
- Chapter 17: The Polynomial Hierarchy
pp. 411-418, IN
pp. 418-424, Hyvärinen
pp. 424-432, Linnanto
- Lecture 12 (30.11.2004)
- Chapter 18: Computation that Counts
pp. 439-447, Kauppinen
pp. 447-451, Kiviharju
Chapter 19: Polynomial Space
pp. 455-462, Hippeläinen
- Lecture 13 (7.12.2004)
-
Chapter 20: A Glimpse Beyond (IN)
Course summary and feedback session