Applications of positive and intuitionistic bounded arithmetic to proof complexity

Abstract

We introduce uniform versions of monotone and deep inference proof systems in the setting of bounded arithmetic, relating the size of propositional proofs to forms of proof-theoretic strength in weak fragments of arithmetic.

This continues the recent program of studying the complexity of propositional deep inference. In particular this work is inspired by previous work where proofs of the propositional pigeonhole principle in the minimal deep inference system, KS, were constructed using rather abstract uniform templates, exemplifying the pertinence of such an approach.

Along the way we are required to draw on a blend of tools from bounded arithmetic, deep inference, and intuitionistic proof theory in order to achieve the required correspondences.