Total NP Search Problems of Bounded Arithmetic and Hard Propositional Principles

Arnold Beckmann, Swansea University. Part of the Algebra, Logic, and Algorithms Seminar series.

Bounded Arithmetic forms a collection of weak theories of Arithmetic related to complexity classes of functions like the Polynomial Time Hierarchy.  Many connections between Bounded Arithmetic and important questions about complexity classes have already been established.  Recent research considers total NP search problems in the context of Bounded Arithmetic.  Total NP search problems have been studied by Papadimitriou et al. as a means to characterise the complexity of natural search problems which cannot be analysed as decision problems.

In my talk I will review the research programme of characterising the provably total NP search problems in Bounded Arithmetic and explain why it is important for current research questions in the area.  We will review recent characterisations of classes of total NP search problems whose totality can be proven in certain Bounded Arithmetic theories, and explain how complete problems for such classes lead to hard problems for propositional proof systems corresponding to Bounded Arithmetic theories.