TFNP: An Update

16^th January 2018, 13:00 Ashton Lecture Theater
Prof. Paul Goldberg
Department of Computer Science
University of Oxford

Abstract

The complexity class TFNP comprises problems in which every instance
has an easily-checkable solution. There are many and varied TFNP problems
that seem to be computationally hard, but NP-hardness is unlikely,
and instead we rely on a diverse set of alternative notions of hardness.
We show how TFNP problems can be expressed in terms of proofs in
formal logic, in a way that's specific to TFNP. This provides a
unifying framework that leads to new and interesting challenges
that generalise existing known TFNP problems.