T-79.5103 Computational Complexity Theory

The second part exam is held on Mon Dec 10, 10:15-12:00 in B353. 

The exam covers 

- Lectures 5-18/Chapters 4-20 in the course book 
  C. Papadimitriou: Computational Complexity, Addison-Wesley, 1994
  (see the related lectures
  http://www.tcs.hut.fi/Studies/T-79.5103/2007AUT/program-2007.html) 

- and the tutorials 3-10, (see
  http://www.tcs.hut.fi/Studies/T-79.5103/2007AUT/tutorials-2007.html)

Some hints for preparing for the exam:

- Material in Chapters 7-9 presents key notions and techniques of the
  course (complexity classes and their relations, reductions,
  completeness, NP-complete problems); study this part carefully.

- For Chapters 10-20 try to build a general view of the material: 
  What are the main complexity classes? What are their relationships? 
  What types of problems belong to given classes? 

- Study the tutorials (and home assignments) carefully.