Logic seminar
Provably total NP search problems in strong theories
Arnold Beckmann
Swansea University
Monday, 11. April 2016 - 13:30 to 15:00
in IM, rear building, ground floor
The class of total NP search problems has been identified by Megiddo and Papadimitriou in the beginning of the 1990ies, who denoted this class TFNP. Total NP search problems whose totality can be proven within a mathematical theory, denoted provably total NP search problems, play an important role in the study of Bounded Arithmetic theories and related questions.
In this talk, I will present characterisations of the provably total NP search problems of strong theories like Peano Arithmetic, and a general research programme related to this.