slideshow 3

Complexity seminar

Does the existence of a complete problem for TFNP class imply the existence of an optimal proof system or vice versa? Part II.

Erfan Khaniki
IM

 

Friday, 13. December 2019 - 13:30 to 15:00

in IM, rear building, ground floor

In this lecture we will construct an oracle with respect to which:
     a. There is no optimal proof system for propositional tautologies.
     b. TFNP=FP.
The existence of this oracle and the one constructed in the previous lecture shows that TFNP_c and CON^N are independent
of each other in relativized worlds.