Bounded arithmetic is an important field of logic closely connected to computational complexity and propositional proof complexity.  A major goal is to understand the hierarchy of bounded arithmetic theories and the connections of their various fragments to these other fields.

We will present some new combinatorial and computational principles characterizing the NP search problems definable in low fragments of bounded arithmetic, as well as some new work connecting these to open problems in propositional proof complexity.  The aim is to fill a gap in current knowledge about these low fragments, which are particularly relevant to propositional proof complexity.

This is joint work with Jan Krajicek and Neil Thapen of the Czech Academy of Sciences.