• Teacher: Doc. Ilkka Niemelä
• Lectures: Wednesdays 16-19, room TB353
• Assistant: Tommi Junttila
• Tutorials: Thursdays 12-14, room TB353
• The course starts on Wed Sep 8, 1999.
• Practical arrangements
• Program of the course, seminar talks, and home assignments
• Classroom exercises, their solutions, home assignments and current point standings
• Course material:
  C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994. (Errata from the publisher, Some further Errata)
• Brochure in Finnish.
• Homepage: http://www.tcs.hut.fi/Teaching/Tik-79.240/
• Home page of Tik-79.240 held autumn 1998.

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
• NP-complete problems
• On P vs NP
• Parallel computation