Showing 2026Show all
2 papers · 1 filter
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 2000)…