zbMATH — the first resource for mathematics

Twelve problems in proof complexity. (English) Zbl 1142.03369
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 13-27 (2008).
Introduction: Proof complexity is a research area that studies the concept of complexity from the point of view of logic. Although it is very much connected with computational complexity, the goals are different. In proof complexity we are studying the question how difficult is to prove a theorem? There are various ways how one can measure the “complexity” of a theorem. We may ask what is the length of the shortest proof of the theorem in a given formal system. Thus the complexity is the size of proofs. This corresponds to questions in computational complexity about the size of circuits, the number of steps of Turing machines etc. needed to compute a given function. But we may also ask how strong theory is needed to prove the theorem. This also has a counterpart in computational complexity – the questions about the smallest complexity class to which a given set or function belongs.
Often the best way to find out what is going on in some field of research is to look at open problems. Therefore my aim in this paper is to compile a list of problems in proof complexity that I consider to be important, but which also seem to be within the reach of our methods. With each problem, I shall define the necessary concepts and mention some related results.
The paper is intended for researchers in computational complexity who want to know what is going on in proof complexity and, perhaps, want to try some open problem there. Essentially all problems have already been stated before, sometimes in different forms.
For the entire collection see [Zbl 1136.68005].

03F20 Complexity of proofs
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
PDF BibTeX Cite
Full Text: DOI