Provably Total NP Search Problems of Bounded Arithmetic

Bounded Arithmetic forms a collection of weak theories of Peano 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 briefly 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 aim to describe a particular result about the provably total NP search problems of Bounded Arithmetic theories related to PSPACE and EXPTIME reasoning.