\P\≠\NP and All Non-Empty Sets in\n \NP\∪\coNP Have P-Optimal Proof Systems Relative to an\n Oracle

2019/09/05 by Titus Dose, Dose, Titus
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Methods in Verification #Logic, Reasoning, and Knowledge #Logic, programming, and type systems

paper · pdf · doi:10.48550/arxiv.1909.02839

openalex publication_date 2019/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

As one step in a working program initiated by Pudl 'ak [Pud17] we construct\nan oracle relative to which \P\≠\NP and all non-empty sets\nin \NP\∪\coNP have \P-optimal proof systems.\n

Related

• P-Optimal Proof Systems for Each coNP-Complete Set and no Complete Problems in NP\capcoNP Relative to an Oracle
• P-Optimal Proof Systems for Each NP-Complete Set but no Complete Disjoint NP-Pairs Relative to an Oracle
• An Oracle with no UP-Complete Sets, but NP=PSPACE
• Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP
• Optimal Proof Systems for Complex Sets are Hard to Find