Fabian Egidy

activity

20222026

collaborators

Showing 2024Show all

2 papers · 1 filter

cs.CC2024

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 $O_{1}$ and $O_{2}$ with the following prop…

cs.CC2024

An Oracle with no $UP$ -Complete Sets, but $NP = PSPACE$

David Dingel, Fabian Egidy, Christian Glaßer

We construct an oracle relative to which $NP = PSPACE$ , but $UP$ has no many-one complete sets. This combines the properties of an oracle by Hartmanis an…

Optimal Proof Systems for Complex Sets are Hard to Find

An Oracle with no UP-Complete Sets, but NP=PSPACE

An Oracle with no $UP$ -Complete Sets, but $NP = PSPACE$