Oracle without Optimal Proof Systems outside Nondeterministic Subexponential Time

We study the existence of optimal proof systems for sets outside of NP. Currently, no set L ∉ 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 NTIME(t) where t is slightly superpolynomial. We construct an oracle O, such that for any set L ⊆ Σ^* at least one of the following two properties holds: L does not have optimal proof systems relative to O. L ∈ UTIMEO(2^2(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 NP.