P-Optimal Proof Systems for Each NP-Complete Set but no Complete Disjoint NP-Pairs Relative to an Oracle

Abstract

Pudlák [Pud17] lists several major conjectures from the field of proof complexity and asks for oracles that separate corresponding relativized conjectures. Among these conjectures are: - $\mathsf{DisjNP}$: The class of all disjoint NP-pairs does not have many-one complete elements. - $\mathsf{SAT}$: NP does not contain many-one complete sets that have P-optimal proof systems. - $\mathsf{UP}$: UP does not have many-one complete problems. - $\mathsf{NP}\cap \mathsf{coNP}$: $\text{NP}\cap \text{coNP}$ does not have many-one complete problems. As one answer to this question, we construct an oracle relative to which $\mathsf{DisjNP}$, $\neg \mathsf{SAT}$, $\mathsf{UP}$, and $\mathsf{NP}\cap \mathsf{coNP}$ hold, i.e., there is no relativizable proof for the implication $\mathsf{DisjNP}\wedge \mathsf{UP}\wedge \mathsf{NP}\cap \mathsf{coNP}\Rightarrow \mathsf{SAT}$. In particular, regarding the conjectures by Pudlák this extends a result by Khaniki [Kha19].

arXiv admin note: substantial text overlap with arXiv:1910.08571, arXiv:1909.02839, arXiv:1903.11860