Optimal Proof Systems for Complex Sets are Hard to Find
Fabian Egidy, Christian Glaßer · arXiv (Cornell University) · 2024
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 properties, where $\mathrm{RE}$ denotes the class of recursively enumerable sets and $\mathrm{NQP}$ the class of sets accepted in non-deterministic quasi-polynomial time. - $O_1$: No set in $\mathrm{PSPACE} \setminus \mathrm{NP}$ has optimal proof systems and $\mathrm{PH}$ is infinite - $O_2$: No set in $\mathrm{RE} \setminus \mathrm{NQP}$ has optimal proof systems and $\mathrm{NP} eq \mathrm{coNP}$ Oracle $O_2$ is the first relative to which complex sets with optimal proof systems do not exist. By oracle $O_1$, no relativizable proof can show that there exist sets in $\mathrm{PSPACE} \setminus \mathrm{NP}$ with optimal proof systems, even when assuming an infinite $\mathrm{PH}$. By oracle $O_2$, no relativizable proof can show that there exist sets outside $\mathrm{NQP}$ with optimal proof systems, even when assuming $\mathrm{NP} eq \mathrm{coNP}$. This explains the difficulty of the following longstanding open questions raised by Krajíček and Pudlák in 1989, Sadowski in 1997, Köbler and Messner in 1998, and Messner in 2000. - Q1: Are there sets outside $\mathrm{NP}$ with optimal proof systems? - Q2: Are there arbitrarily complex sets outside $\mathrm{NP}$ with optimal proof systems? Moreover, relative to $O_2$, there exist arbitrarily complex sets $L otin \mathrm{NQP}$ having almost optimal algorithms, but none of them has optimal proof systems. This explains the difficulty of Messner's approach to translate almost optimal algorithms into optimal proof systems.