Provably Total NP Search Problems of Bounded Arithmetic and beyond

• Professor Arnold Beckmann

• University of Swansea, Head of Department of Computer Science

Abstract: 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. I will describe recent results about the provably total NP search problems of a Bounded Arithmetic theories related to PSPACE and EXPTIME reasoning. I will also describe this program for theories beyond Bounded Arithmetic like Peano arithmetic, and what impact this might have on Complexity Theory.