Nonconstructive proofs of existence for provably total search problems

232 views · Published 13 April 2016 · 1:22:46 · Indexed 16 November 2026

Channel: ФКН НИУ ВШЭ · 2016 · Education

Watch on YouTube

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 discuss two recent results about the Tucker problem and about the Frege Proof Consistency search problem.

Speaker: Sam Buss, University of California, San Diego.

Workshop on Theoretical Computer Science 2016: https://cs.hse.ru/en/big-data/tcs-lab/tcs2016/
Faculty of Computer Science: https://cs.hse.ru/en/
Follow us: https://www.facebook.com/hsefcs, https://twitter.com/CS_HSE

More from this channel