T-79.240 Special Course on Computational Complexity

Tutorial Program, Autumn 2004

• 14.9.
  • 1.4.10, functions (a), (f) and (j)
  • 2.8.7
  • Solutions in postscript
• 21.9.
  • 3.4.1 (a), (d) and (f)
  • 3.4.6
  • Solutions in postscript
• 28.9. No tutorials!
• 5.10.
  • A translation from NFA to Boolean circuits
  • 7.4.6
  • 7.4.3 (a)
  • Solutions in postscript
• 12.10.
  • A proof that HORNSAT is P-complete
  • 8.4.8
  • Solutions in postscript
• 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.
  • 10.4.4
  • 10.4.6
  • Solutions in postscript
• 11.11. at 12
  • 11.5.12
  • 11.5.13
  • 11.5.15
  • Solutions in postscript
• 16.11.
  • 12.3.2 (a)
  • 13.4.3
  • 13.4.5
  • Solutions in postscript
• 23.11.
  • 14.5.9
  • 15.5.6 (a)
  • 17.3.3
  • 17.3.6
  • Solutions in postscript