Autumn 2005 (periods I and II)

[General Information] [Lecture Notes] [Tutorials] [Homework] [TOPI]

This is an advanced course on computational complexity covering topics such as NP-completeness, randomized algorithms, cryptography, approximation algorithms, parallel algorithms, polynomial hierarchy, PSPACE-completeness.

General Information

• Please use the TOPI system for registration.
• This course replaces the former course T-79.240 Special Course in Computational Complexity.
• Lectures: Prof. (pro tem), D.Sc.(Tech.) Tomi Janhunen, Wednesdays, 10-12, and Thursdays (basically every 2nd week), 10-12, room TB353
• Tutorials: M.Sc.(Tech.) Matti Järvisalo, Mondays, 14-16, room TB353.
• Course material: C. Papadimitriou: Computational Complexity, Addison-Wesley, 1994.
  (Errata from the publisher, some further corrections)
• Brochure in Finnish
• Program for lectures and seminar talks
• Grades for the seminar presentations
• The topics of seminar talks were assigned on the 20th of October, 2005, using a protocol (a series of lotteries). All topics have now been booked. If there is still someone needing a topic he/she should contact the lecturer urgently.

Lecture Notes

• Practical arrangements (.ps / .pdf)
• Examples of Problems (.ps / .pdf)
• Turing Machines (.ps / .pdf)
• More about Turing Machines (.ps / .pdf)
• Boolean Logic (.ps / .pdf)
• Relations between Complexity Classes (.ps / .pdf)
• Reductions and Completeness (.ps / .pdf)
• NP-complete problems (.ps / .pdf)
• coNP and function problems (.ps / .pdf)
• Parallel computation and logarithmic space (.ps / .pdf)

Please remember to check the tentative schedule for presenting this material. In particular, there are exceptional Thursdays as no lecture is given.

Course Feedback

We welcome feedback which is collected centrally in Finnish, Swedish, or English; the questionnaire is activated on the 9th of December, 2005.

• To obtain a 0.5 point homework bonus you are supposed to fill in the form by the 2nd of January, 2006 (24:00 hours).

Tutorials

• Tutorials are held on Mondays 14-16 by Matti Järvisalo.
• List of tutorial exercises

Homework

• Weekly homework is based on selected exercises from Papadimitriou's book.
• Please note that homework exercises are personal and thus copying answers (plagiarism) is prohibited!