КТИ 2016 : Nonconstructive proofs of existence for provably total search problems

Sam Buss University of California, San Diego The class TFNP of total NP search problems consists of multivalued functions (total relations) with polynomial time recognizable graphs. In the complexity theoretic setting, the totality (existence) is usually established via a combinatorial principle, but it can also be established in a fragment of bounded arithmetic. This talk will give an introduction to these classes, from both points of view (complexity theoretic and bounded arithmetic). We will also dis