6 papers
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…
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)…
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…
An Oracle with no -Complete Sets, but
David Dingel, Fabian Egidy, Christian Glaßer
We construct an oracle relative to which , but has no many-one complete sets. This combines the properties of an oracle by Hartmanis an…
Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP
Fabian Egidy, Christian Glaßer, Martin Herold
We study the existence of optimal and p-optimal proof systems for classes in the Boolean hierarchy over . Our main results concern , i.e., the second leve…
Oracle with , but no Many-One Completeness in UP, DisjNP, and DisjCoNP
Anton Ehrmanntraut, Fabian Egidy, Christian Glaßer
We construct an oracle relative to which , but there are no many-one complete sets in , no many-one complete disjoint $\ma…