Fundamental problems in proof complexity
Jan Krajı́ček · Cambridge University Press eBooks · 2010
In this last part of the book we shall consider strong proof systems. We start by recalling in this chapter briefly a very general background of proof complexity, and by spelling out a few open problems that we consider fundamental for further development. This exposition is included in order to give the reader some idea of what motivates the choice of topics we study in later chapters. Details can be found in the references given in the Introduction (or in the text below). Cook and Reckhow [31] defined a general proof system for propositional logic to be a polynomial-time computable function P defined on {0,1}* whose range is exactly the set TAUT of propositional tautologies in the DeMorgan language 0, 1, ∧, ∨, ¬ (see Chapter 17). Any string that P maps to a tautology τ is called a P-proof of τ. This definition subsumes the usual calculi for propositional logic that one encounters in textbooks and, in particular, those defined in Chapter 17: given such a calculus interpret it as a function that maps a string that is a valid proof to the formula being proved, and all other strings to some fixed tautology (for example, to 1). Such a function will satisfy the Cook–Reckhow definition as in all logical calculi it is recognizable by a p-time algorithm whether a string is a valid proof or not. Note that the fact that the range of the function constructed in this way from a propositional calculus is exactly the set TAUT is equivalent to the soundness and the completeness of the calculus.