T-79.240 Tutorials

T-79.240 Special Course on Computational Complexity

Exercise numbers refer to the exercises in Papadimitriou's book.

Week 38 (16.9.)
- 1.4.10, functions (a), (f) and (j)
- 2.8.7
- Solutions in postscript
Week 39 (23.9.)
- 3.4.1 (a), (d) and (f)
- 3.4.6
- Solutions in postscript
Week 40 (30.9.) cancelled
Week 41 (7.10.)
- A translation from NFA to Boolean circuits
- 7.4.6
- 7.4.3 (a)
- Solutions in postscript
Week 42 (14.10.)
- A proof that HORNSAT is P-complete
- 8.4.8
- Solutions in postscript
Week 43 (21.10.)
- A proof that MAX2SAT is NP-complete
- A proof that LONGEST PATH is NP-complete
- A proof that SUBGRAPH ISOMORPHISM is NP-complete
- Solutions in postscript
Week 44 (28.10.)
- A proof that INDEPENDENT SET is NP-complete
- A proof that FEEDBACK VERTEX SET is NP-complete
- A proof that PARTITION INTO TRIANGLES is NP-complete
- Solutions in postscript
Week 45 (4.11.)
- 10.4.4
- 10.4.6
- Solutions in postscript
Week 46 (11.11.)
- 11.5.12
- 11.5.13
- 11.5.15
- Solutions in postscript
Week 47 (18.11.)
- 12.3.2 (a)
- 13.4.3
- 13.4.5
- Solutions in postscript
Week 48 (25.11.)
- 14.5.9
- 15.5.6 (a)
- 17.3.3
- 17.3.6
- Solutions in postscript