TCS / Studies / T-79.5103 Computational Complexity Theory
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science


Computational Complexity Theory

(5 cr) P

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.
Back to menu.

Lecture Notes

(Slides in English)

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

Back to menu.

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).
Back to menu.


Back to menu.


  • 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!
Back to menu.
[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 05 January 2006. Tomi Janhunen