P-Optimal Proof Systems for Each Set in NP but no Complete Disjoint NP-pairs Relative to an Oracle
Titus Dose · arXiv (Cornell University) · 2019
Pudlak [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}$: there exist no many-one complete disjoint NP-pairs. - $\mathsf{SAT}$: each many-one complete set for NP has no P-optimal proof systems. - $\mathsf{UP}$: there exist no many-one complete problems in UP. - $\mathsf{NP}\cap\mathsf{coNP}$: there exist no many-one complete problems in $\text{NP}\cap\text{coNP}$. As one answer to this question, we construct an oracle relative to which $\mathsf{DisjNP}$, $ eg \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 Pudlak this extends a result by Khaniki [Kha19]. Since Khaniki [kha19] constructs an oracle showing that the implication $\mathsf{SAT}\Rightarrow\mathsf{DisjNP}$ has no relativizable proof, we obtain that the conjectures $\mathsf{DisjNP}$ and $\mathsf{SAT}$ are independent in relativized worlds, i.e., none of the implications $\mathsf{DisjNP}\Rightarrow\mathsf{SAT}$ and $\mathsf{SAT}\Rightarrow\mathsf{DisjNP}$ can be proven relativizably.