• Teacher: Prof. Ilkka Niemelä
• Lectures: Wednesdays 16-19, room TB353
• Assistant: Tommi Junttila
• Tutorials: Tuesdays 16-18, room TB353
• The course starts on Wed Sep 12, 2001.
• Course material:
  C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994. (Errata from the publisher, Some further Errata)
• Brochure in Finnish.
• Practical arrangements
• Program of the course, seminar talks, and home assignments
• Classroom exercises, their solutions, home assignments and current point standings
• Extra bonus assignments
• Homepage: http://www.tcs.hut.fi/Teaching/T-79.240/
• Previous years: [Autumn 1998] [Autumn 1999] [Autumn 2000]

Lecture Notes

• Introduction
• Basics of Turing machines
• More on Turing machines, time and space complexity, undecidability
• Boolean logic
• Relations between complexity classes
• Reductions and completeness
• On P vs NP
• Parallel computation and logarithmic space
• Polynomial Space
• A Glimpse Beyond