T-79.5103 Computational Complexity Theory
Tentative schedule (Autumn 2006)
Period I
- Lecture 1 (19.9.2006)
- Introduction (IN)
Chapter 1: Problems and algorithms (IN)
- Lecture 2 (20.9.2006)
- Chapter 2: Turing machines (IN)
- Lecture 3 (26.9.2006)
- Chapter 2: More about Turing machines (IN)
Chapter 3: Undecidability (IN)
- Lecture 4 (27.9.2006)
- Chapter 4: Boolean logic (IN)
Chapter 7: Complexity classes (IN)
- First Quarter Exam (3.10.2006)
- Lecture 5 (4.10.2006)
- Chapter 7: Relations between Complexity classes (IN)
Chapter 8: Reductions (IN)
- Note: No lectures on Tue 10.10.2006
- Lecture 6 (11.10.2006)
- Chapter 8: Completeness (IN)
- Lecture 7 (17.10.2006)
- Chapter 9: NP-complete problems (IN)
- Lecture 8 (18.10.2006)
- Chapter 9: NP-complete problems - cont'd (IN)
- Lecture 9 (24.10.2006)
- Seminar Talk Lottery (at 10:15)
- Chapter 10: coNP and function problems (IN)
- Note: Tutorials instead of lectures on Wed 25.10.2006
Period II
- Lecture 10 (7.11.2006)
- Chapter 11: Randomized computation (seminar talks)
S1: pp. 241-248 (Tuominen)
S2: pp. 248-256 (Kähkönen)
- Lecture 11 (8.11.2006)
- Chapter 11: Randomized computation (seminar talks)
S3: pp. 256-263 (Ihantola)
S4: pp. 263-271 (Launiainen)
- Lecture 12 (14.11.2006)
- Chapter 12: Cryptography (seminar talks)
S5: pp. 279-287 (Hällfors)
S6: pp. 287-293 (van der Meer)
- Lecture 13 (15.11.2006)
- Chapter 13: Approximability (seminar talks)
S7: pp. 299-307 (Pitkämäki)
S8: pp. 307-315 (Lindfors)
- Note: No lectures on Tue 21.11.2006
- Lecture 14 (22.11.2006)
- Chapter 13: Approximability (seminar talks)
S9: pp. 315-322 (Hanhijärvi)
Chapter 14: On P vs. NP (seminar talks)
S10: pp. 329-336 (Heikinheimo)
- Lecture 15 (27.11.2006)
- This is on Monday at 14-16 in T-B353
Chapter 14: On P vs. NP (seminar talks)
S11: pp. 336-343 (Hakala)
Chapter 15: Parallel computation (IN)
- Lecture 16 (28.11.2006)
- Chapter 16: Log space (seminar talks)
S12: pp. 395-404 (Lahtinen)
Chapter 17: The polynomial hierarchy (seminar talks)
S13: pp. 411-418 (Lahola)
- Lecture 17 (29.11.2006)
- Chapter 17: The polynomial hierarchy (seminar talks)
S14: pp. 418-424 (Busch)
S15: pp. 424-432 (Viinamäki)
- Note: No lectures on Tue 5.12. and Wed 6.12.2006
- Lecture 18 (12.12.2006)
- Chapter 18: Computation that counts (seminar talks)
S16: pp. 439-447 (Raitanen)
S17: pp. 447-451 (IN)
- Lecture 19 (13.12.2006)
- Chapter 19: Polynomial Space (seminar talks)
S18: pp. 455-462 (IN)
Chapter 20: A Glimpse Beyond (IN)
Course summary and feedback session