slideshow 3

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.