T-79.240 Special Course on Computational Complexity
Tutorial Program, Autumn 2004
Exercise numbers refer to the exercises in Papadimitriou's book.
- 14.9.
- 21.9.
- 28.9. No tutorials!
- 5.10.
- 12.10.
- 19.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
- 26.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
- 2.11.
- 11.11. at 12
- 16.11.
- 23.11.