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.
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.
published by Pavel Pudlák on Wed, 11/12/2019 - 20:07