T-79.5103 Computational Complexity Theory

Tentative schedule (Autumn 2007)

Period I

Lecture 1 (17.9.2007)

Introduction [pdf] [ps]
Chapter 1: Problems and algorithms [pdf] [ps]

Lecture 2 (19.9.2007)

Chapter 2: Turing machines [pdf] [ps]

Lecture 3 (24.9.2007) at 14:15 (instead of tutorial)

Chapter 2: More about Turing machines
[pdf] [ps]

Lecture 4 (26.9.2007)

Chapter 3: Undecidability
(For slides see Lecture 3 above)

First Quarter Exam (3.10.2007)

Lecture 5 (8.10.2007)

Chapter 4: Boolean logic [pdf] [ps]

Chapter 7: Relations between complexity classes [pdf] [ps]

Lecture 6 (10.10.2007)

Chapter 7: Relations between complexity classes - cont'd

Lecture 7 (15.10.2007)

Chapter 8: Reductions and completeness [pdf] [ps]

Lecture 8 (17.10.2007)

Chapter 9: NP-complete problems [pdf] [ps]

Lecture 9 (22.10.2007)

Chapter 9: NP-complete problems - cont'd

Lecture 10 (24.10.2007)

Chapter 10: coNP and function problems [pdf] [ps]

Deadline for Home Assignment 1 on Chapters 3-8 (24.10.2007)

Period II

Lecture 11 (5.11.2007)

Chapter 11: Randomized computation [pdf] [ps]

Deadline for Home Assignment 2 on Chapters 9-10 (5.11.2007)

Lecture 12 (7.11.2007)

Chapter 12: Cryptography [pdf] [ps]

Lecture 13 (12.11.2007)

Chapter 13: Approximability [pdf] [ps]

Resubmission Deadline for Home Assignment 1 (12.11.2007)

Lecture 14 (14.11.2007)

Chapter 14: On P vs. NP [pdf] [ps]

Lecture 15 (19.11.2007)

Chapter 15: Parallel computation

Chapter 16: Log space
[pdf] [ps]

Lecture 16 (21.11.2007)

Chapter 17: The polynomial hierarchy [pdf] [ps]

Lecture 17 (26.11.2007)

Chapter 18: Computation that counts [pdf] [ps]

Lecture 18 (28.11.2007)

Chapter 19: Polynomial Space [pdf] [ps]

Chapter 20: A Glimpse Beyond [pdf] [ps]
Course summary and feedback session

Resubmission Deadline for Home Assignment 2 (5.12.2007)

Deadline for Home Assignment 3 on Chapters 11-19 (5.12.2007)

Final Exam (10.12.2007)

Resubmission Deadline for Home Assignment 3 (21.12.2007)