T-79.7001 Postgraduate Course in Theoretical Computer Science
(2 - 10 cr) P V

Autumn 2007

The topic of Autumn 2007 is Propositional Proof Complexity.

Propositional proof complexity studies the lengths of proofs in propositional logic. It is an area that is related to major open questions of computational complexity theory and to practical properties of automated theorem provers such as satisfiability checkers. Moreover, connections between proof complexity and circuit complexity have been discovered and concepts and techniques in proof complexity have contributed to several other areas of computer science, including cryptography, automated reasoning and AI, complexity of search classes within NP, the analysis of heuristics and algorithms for NP-hard problems, and bounded arithmetic.

In the course we cover fundamentals of propositional proof complexity and some interesting connections with the other areas.

The course is taken by giving seminar talks.

• Literature:
  Clote, Peter and Kranakis, Evangelos: Boolean Functions and Computation Models. Springer 2002.
  Articles.
• Seminars: On Monday, 16-20, room TB353.
• The course starts on Sep 17, 2007 at 16:30.
• Teacher: Prof. Ilkka Niemelä
  Email: Ilkka.Niemela (at) tkk.fi
  Homepage: http://www.tcs.hut.fi/~ini/
• Course home page: http://www.tcs.hut.fi/Studies/T-79.7001/