Proof complexity generators: definitions and facts
Jan Krajı́ček · Cambridge University Press eBooks · 2010
We have chosen the model-theoretic approach (Chapter 18 and Theorem 28.2.1) as a framework in which to think about lower bounds for EF. However, an all important ingredient is also to have examples of specific candidate tautologies that could be plausibly conjectured to be hard for EF. The experience with lower bound proofs for weaker proof systems shows that one needs specific, combinatorially transparent, formulas to work with. From a model-theoretic perspective this is not surprising: a lower bound is, in effect, a construction of a model where the formula is not valid, so in order to hope to describe such a model we had better understand what the formula means. Of course, one may expect that a random 3DNF (with n variables and c · n clauses, for suitable c ) is hard for any proof system, and for some specific systems this has indeed been established (see e.g. Chvatal and Szemeredi [22]). However, lower bounds for random formulas are obtained by verifying that in a lower bound proof discovered originally for some different and specific formula the only properties of the formula that are used are those that are also shared by the random one. Unfortunately the formulas that worked for weak proof systems are demonstrably easy to prove in EF. The foremost example is the PHP principle we have seen earlier (Chapter 19). However, PHP has short proofs in EF (see Cook and Reckhow [31]) and, infact, even in F (see Buss [12]).