2 papers
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 and with the following prop…
cs.CC2024
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…