
T79.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 NPhard
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, 1620, 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/T79.7001/
