No feasible monotone interpolation for simple combinatorial reasoning
The feasible monotone interpolation method has been one of the main tools to prove the exponential lower bounds for relatively weak propositional systems. Arai (Theoret. Comput. Sci. 170 (1996) 129-144) introduced a simple combinatorial reasoning system, GCNF+permutation, as a candidate for an automatizable, though powerful, propositional calculus. We show that the monotone interpolation method is not applicable to prove the superpolynomial lower bounds for Simple Combinatorial Reasoning. At the same time, we show that Cutting Planes, Hilbert's Nullstellensatz and the polynomial calculus do not p-simulate Simple Combinatorial Reasoning. (C) 2000 Elsevier Science B.V. All rights reserved.
automated theorem proving proof complexity craig's interpolation theorem proof theory