T-79.240 Special Course on Computational Complexity (3 cr)

Autumn 2004

[General Information] [Lectures] [Tutorials] [Home assignments] [Other Interesting Stuff] [TOPI]

Previous years: [Autumn 2003] [Autumn 2002] [Autumn 2001] [Autumn 2000] [Autumn 1999] [Autumn 1998]

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

• NEWS: Remember to give feedback about the course by filling out a feedback questionnaire (palautelomake) available through the feedback pages of the Department of Computer Science and Engineering.

  The feedback questionnaire of the course is open from Dec 1, 2004 to Dec 22, 2004.

• Lectures by Prof. Ilkka Niemelä: Tuesdays 12-15, room TB353
• Tutorials by Matti Järvisalo: Tuesdays 16-18, room TB353
• The course starts on Tue Sep 14, 2004.
• Course material:
  C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994. (Errata from the publisher, Some further Errata)
  
• Brochure in Finnish
• Practical arrangements for passing the course
• Lecture/seminar talk schedule
• Grading for the course [PDF]
• Extra bonus assignments

Lecture Notes

• Introduction to Computational Complexity
• 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
• coNP and function problems
• On P vs NP
• Parallel computation and logarithmic space
• Polynomial Space
• A Glimpse Beyond

Tutorials

• Tutorials are held on Tuesdays 16-18 in room TB353 by Matti Järvisalo. The first tutorials are on Sep 14.
• Tutorial exercises and their solutions

Home Assignments

• See the program for the home assignments for each week.
• See the practical arrangements for details about submitting and grading home assignments.

Other Interesting Stuff

• The standard textbook on NP-completeness is
  Michael Garey and David Johnson: Computers and Intractability - A Guide to the Theory of NP-completeness; Freeman, 1979.
• David Johnson runs a column (The NP-completeness column: An ongoing guide) in Journal of Algorithms.
• A compendium of NP optimization problems
• Some text books available in the web
  • Herbert S. Wilf: Algorithms and Complexity
  • Ian Parberry's books (Problems on Algorithms, Lecture Notes on Algorithm Analysis and Complexity Theory, Parallel Complexity Theory)
  • Eitan Gurari: An Introduction to the Theory of Computational
  • Ingo Wegener: The Complexity of Boolean Functions
• Computational Complexity Column of Bulletin of the European Association for Theoretical Computer Science
• Electronic Colloquium on Computational Complexity
• Lance Fortnow's Computational Complexity weblog
• Alan Turing Home Page (maintained by Andrew Hodges)