$\mathrm{P}$-Optimal Proof Systems for Each $\mathrm{coNP}$-Complete Set and no Complete Problems in $\mathrm{NP}\cap\mathrm{coNP}$ Relative to an Oracle

Titus Dose

paper

$P$ -Optimal Proof Systems for Each $coNP$ -Complete Set and no Complete Problems in $NP \cap coNP$ Relative to an Oracle

arXiv:1910.08571

Abstract

We build on a working program initiated by Pudlák [Pud17] and construct an oracle relative to which each $coNP$ -complete set has $P$ -optimal proof systems and $NP \cap coNP$ does not have complete problems.

arXiv admin note: substantial text overlap with arXiv:1904.06175, arXiv:1909.02839

P-Optimal Proof Systems for Each coNP-Complete Set and no Complete Problems in NP∩coNP Relative to an Oracle

Abstract

$P$ -Optimal Proof Systems for Each $coNP$ -Complete Set and no Complete Problems in $NP \cap coNP$ Relative to an Oracle