3 papers
cs.CC2026
Recursive Jump Operators and Optimal Proof Systems
Fabian Egidy
We study the relationship between the existence of optimal proof systems and recursive jump operators, two central open problems in proof complexity. For a set L, an optimal proof…
cs.CC2026
The SPARSE-Relativization Framework and Applications to Optimal Proof Systems
Fabian Egidy
We investigate the following longstanding open questions raised by KrajÃÄek and Pudlák (J. Symb. L. 1989), Sadowski (FCT 1997), Köbler and Messner (CCC 1998) and Messner (PhD 2…
cs.CC2025
Optimal Proof Systems for Complex Sets are Hard to Find
Fabian Egidy, Christian GlaÃer
We provide the first evidence for the inherent difficulty of finding complex sets with optimal proof systems. For this, we construct oracles and with the following prop…