Tik-79.240 Special Course on Computational Complexity

Autumn 1999
Program

8.9.99

Introduction (IN)
Chapter 2: Basics of Turing machines (IN)
Home assignments: 1.4.10 (b),(c),(d),(g) and 2.8.8 (a)

15.9.99

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)

22.9.99

Chapter 4 & 7: Boolean Logic; relations between complexity classes (IN)
Home assignments: 4.4.5 and 7.4.5

29.9.99

Chapter 8: Reductions and completeness (IN)
Home assignments: 8.4.2 and 8.4.3

6.10.99

Chapter 9: NP-complete problems (IN)
Home assignments: 9.5.2 and 9.5.6

13.10.99 (Seminar talks start)

Chapter 10: coNP and function problems
pp. 219-227, Jussila
pp. 227-234, Latvala
Chapter 11: Randomized computation
pp. 241-248, Tauriainen
Home assignments: 9.5.7 and 9.5.10 (a)

20.10.99

pp. 248-256, Haanpää
pp. 256-263, Latvala
pp. 263-271, Bamer
Home assignments: 10.4.13 and 10.4.19 (a)

27.10.99

Chapter 12: Cryptography
pp. 279-287, Viitaniemi
pp. 287-293, IN
Chapter 13: Approximability
pp. 299-307, Viljanen
Home assignments: 11.5.14 and 11.5.16 (a)

3.11.99

pp. 307-315, Bamer
pp. 315-322, Lahtinen
Home assignments: 12.3.9 (b) and 13.4.13 (a)

10.11.99

Chapters 14-16 (IN)
Home assignments: 14.5.5 (only the KNAPSACK part) and 15.5.9 (a)

17.11.99

Chapter 17: The Polynomial Hierarchy
pp. 411-418, Tauriainen
pp. 418-424, Haanpää
pp. 424-432, IN
Home assignments: 17.3.2 (a), (b) and 17.3.12

24.11.99

Chapter 18: Computation that Counts
pp. 439-447, Jussila
pp. 447-451, Viitaniemi
Chapter 19: Polynomial Space
pp. 455-462, Viljanen
Home assignments: 18.3.6 and 19.4.5

1.12.99

Lectures cancelled

8.12.99

Course summary and feedback session
Home assignments: 9.5.18 (a), (b) and 9.5.34 (a)