Titus Dose

collaborators

Showing cs.CCShow all

4 papers · 1 filter

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

An Oracle Separating Conjectures about Incompleteness in the Finite Domain

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

An Oracle Separating Conjectures about Incompleteness in the Finite Domain

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