Titus Dose

collaborators

4 papers

cs.CC2019

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

Titus Dose

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 $\m…

cs.CC2019

$P \neq = NP$ and All Non-Empty Sets in $NP \cup coNP$ Have P-Optimal Proof Systems Relative to an Oracle

Titus Dose

As one step in a working program initiated by Pudlák [Pud17] we construct an oracle relative to which $P \neq = NP$ and all non-empty sets in $\mathrm{NP}\cup\mathrm{c…

cs.CC2019

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

Titus Dose

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…

cs.CC2019

Complete Disjoint coNP-Pairs but no Complete Total Polynomial Search Problems Relative to an Oracle

Titus Dose

All versions of this paper contain errors. Therefore, the existence of an oracle relative to which (i) there exist complete disjoint coNP-pairs and (ii) there exist no complete tot…

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

P=NP and All Non-Empty Sets in NP∪coNP Have P-Optimal Proof Systems Relative to an Oracle

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

Complete Disjoint coNP-Pairs but no Complete Total Polynomial Search Problems Relative to an Oracle

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

$P \neq = NP$ and All Non-Empty Sets in $NP \cup coNP$ Have P-Optimal Proof Systems Relative to an Oracle