Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



TR98-067 | 12th November 1998 00:00

Propositional Proof Complexity: Past, Present and Future


Authors: Paul Beame
Publication: 1st December 1998 10:18
Downloads: 1174


Proof complexity, the study of the lengths of proofs in
propositional logic, is an area of study that is fundamentally connected
both to major open questions of computational complexity theory and
to practical properties of automated theorem provers. In the last
decade, there have been a number of significant advances in proof
complexity lower bounds. Moreover, new connections between proof
complexity and circuit complexity have been uncovered, and the interplay
between these two areas has become quite rich. In addition, attempts
to extend existing lower bounds to ever stronger proof systems of proof
have spurred the introduction of new and interesting proof systems,
adding both to the practical aspects of proof complexity as well as
to a rich theory.

This note attempts to survey these developments
and to lay out some of the open problems in the area.
This is an updated version of our article appearing in
the Computational Complexity Column of the Bulletin of
the EATCS, 1998.

ISSN 1433-8092 | Imprint