Oracle without Optimal Proof Systems outside Nondeterministic Subexponential Time
<|reference_start|>Oracle without Optimal Proof Systems outside Nondeterministic Subexponential Time: We study the existence of optimal proof systems for sets outside of $\mathrm{NP}$. Currently, no set $L \notin \mathrm{NP}$ is known that has optimal proof systems. Our main result shows that this is not surprising, because we can rule out relativizable proofs of optimality for all sets outside $\mathrm{NTIME}(t)$ where $t$ is slightly superpolynomial. We construct an oracle $O$, such that for any set $L \subseteq \Sigma^*$ at least one of the following two properties holds: $L$ does not have optimal proof systems relative to $O$. $L \in \mathrm{UTIME}^O(2^{2(\log n)^{8+4\log(\log(\log(n)))}})$. The runtime bound is slightly superpolynomial. So there is no relativizable proof showing that a complex set has optimal proof systems. Hence, searching for non-trivial optimal proof systems with relativizable methods can only be successful (if at all) in a narrow range above $\mathrm{NP}$.<|reference_end|>
@article{egidy2024oracle,
    title={Oracle without Optimal Proof Systems outside Nondeterministic
  Subexponential Time},
    author={Fabian Egidy and Christian Gla{ss}er},
    journal={arXiv preprint arXiv:2408.07408},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.07408},
    primaryClass={cs.CC}
}