Zobrazeno 1 - 5
of 5
pro vyhledávání: '"Egidy, Fabian"'
Autor:
Egidy, Fabian, Glaßer, Christian
We provide the first evidence for the inherent difficulty of finding complex sets with optimal proof systems. For this, we construct oracles $O_1$ and $O_2$ with the following properties, where $\mathrm{RE}$ denotes the class of recursively enumerabl
Externí odkaz:
http://arxiv.org/abs/2408.07408
We construct an oracle relative to which $\mathrm{NP} = \mathrm{PSPACE}$, but $\mathrm{UP}$ has no many-one complete sets. This combines the properties of an oracle by Hartmanis and Hemachandra [HH88] and one by Ogiwara and Hemachandra [OH93]. The or
Externí odkaz:
http://arxiv.org/abs/2404.19104
We study the existence of optimal and p-optimal proof systems for classes in the Boolean hierarchy over $\mathrm{NP}$. Our main results concern $\mathrm{DP}$, i.e., the second level of this hierarchy: If all sets in $\mathrm{DP}$ have p-optimal proof
Externí odkaz:
http://arxiv.org/abs/2304.14702
We construct an oracle relative to which $\mathrm{P} = \mathrm{NP} \cap \mathrm{coNP}$, but there are no many-one complete sets in $\mathrm{UP}$, no many-one complete disjoint $\mathrm{NP}$-pairs, and no many-one complete disjoint $\mathrm{coNP}$-pai
Externí odkaz:
http://arxiv.org/abs/2203.11079
We construct an oracle relative to which P = NP ∩ coNP, but there are no many-one complete sets in UP, no many-one complete disjoint NP-pairs, and no many-one complete disjoint coNP-pairs. This contributes to a research program initiated by Pudlák
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ffb29ee0f8428f951d1fd80ae78b1c1d