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? 

Erfan Khaniki
IM

 

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

in IM, rear building, 1st floor (!)

In this talk, we will investigate the relationship between proof complexity conjectures that are mentioned in the "Incompleteness in the finite domain" paper. In particular, we are interested in the relationship between the nonexistence of a complete problem for TFNP class (TFNP_c)  and the nonexistence of an optimal proof system for propositional tautologies (CON^N). For this matter,  we will construct two oracles V and W such that:

1. With respect to the V
     a. There is no complete problem for disjoint NP-pairs.
     b. E=NE.
2. With respect to the W
     a. There is no optimal proof system for propositional tautologies.
     b. TFNP=FP.
The existence of these oracles shows that TFNP_c and CON^N are independent of each other in the relativized worlds.