2024/08/14 by Fabian Egidy, Egidy, Fabian, Christian Glaßer +1
Computer Science · #Advanced Database Systems and Queries #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.2408.07408
openalex publication_date 2024/08/14 · openalex created_date 2024/09/18 · openalex updated_date 2026/07/28
We provide the first evidence for the inherent difficulty of finding complex sets with optimal proof systems. For this, we construct oracles O1 and O2 with the following properties, where RE denotes the class of recursively enumerable sets and NQP the class of sets accepted in non-deterministic quasi-polynomial time. - O1: No set in PSPACE ∖ NP has optimal proof systems and PH is infinite - O2: No set in RE ∖ NQP has optimal proof systems and NP ≠ coNP Oracle O2 is the first relative to which complex sets with optimal proof systems do not exist. By oracle O1, no relativizable proof can show that there exist sets in PSPACE ∖ NP with optimal proof systems, even when assuming an infinite PH. By oracle O2, no relativizable proof can show that there exist sets outside NQP with optimal proof systems, even when assuming NP ≠ 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 NP with optimal proof systems? - Q2: Are there arbitrarily complex sets outside NP with optimal proof systems? Moreover, relative to O2, there exist arbitrarily complex sets L ∉ 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.