Search Results

Documents authored by Egidy, Fabian

Document
DOI: 10.4230/LIPIcs.MFCS.2024.50
An Oracle with no UP-Complete Sets, but NP = PSPACE

Authors: David Dingel, Fabian Egidy, and Christian Glaßer

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
We construct an oracle relative to which NP = PSPACE, but UP has no many-one complete sets. This combines the properties of an oracle by Hartmanis and Hemachandra [J. Hartmanis and L. A. Hemachandra, 1988] and one by Ogiwara and Hemachandra [Ogiwara and Hemachandra, 1991]. The oracle provides new separations of classical conjectures on optimal proof systems and complete sets in promise classes. This answers several questions by Pudlák [P. Pudlák, 2017], e.g., the implications UP ⟹ CON^𝖭 and SAT ⟹ TFNP are false relative to our oracle. Moreover, the oracle demonstrates that, in principle, it is possible that TFNP-complete problems exist, while at the same time SAT has no p-optimal proof systems.
Cite as

David Dingel, Fabian Egidy, and Christian Glaßer. An Oracle with no UP-Complete Sets, but NP = PSPACE. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 50:1-50:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dingel_et_al:LIPIcs.MFCS.2024.50,
  author =	{Dingel, David and Egidy, Fabian and Gla{\ss}er, Christian},
  title =	{{An Oracle with no UP-Complete Sets, but NP = PSPACE}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{50:1--50:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.50},
  URN =		{urn:nbn:de:0030-drops-206063},
  doi =		{10.4230/LIPIcs.MFCS.2024.50},
  annote =	{Keywords: Computational Complexity, Promise Classes, Complete Sets, Oracle Construction}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.44
Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP

Authors: Fabian Egidy, Christian Glaßer, and Martin Herold

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We study the existence of optimal and p-optimal proof systems for classes in the Boolean hierarchy over NP. Our main results concern DP, i.e., the second level of this hierarchy: - If all sets in DP have p-optimal proof systems, then all sets in coDP have p-optimal proof systems. - The analogous implication for optimal proof systems fails relative to an oracle. As a consequence, we clarify such implications for all classes 𝒞 and 𝒟 in the Boolean hierarchy over NP: either we can prove the implication or show that it fails relative to an oracle. Furthermore, we show that the sets SAT and TAUT have p-optimal proof systems, if and only if all sets in the Boolean hierarchy over NP have p-optimal proof systems which is a new characterization of a conjecture studied by Pudlák.
Cite as

Fabian Egidy, Christian Glaßer, and Martin Herold. Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{egidy_et_al:LIPIcs.MFCS.2023.44,
  author =	{Egidy, Fabian and Gla{\ss}er, Christian and Herold, Martin},
  title =	{{Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.44},
  URN =		{urn:nbn:de:0030-drops-185784},
  doi =		{10.4230/LIPIcs.MFCS.2023.44},
  annote =	{Keywords: Computational Complexity, Boolean Hierarchy, Proof Complexity, Proof Systems, Oracle Construction}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.45
Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP

Authors: Anton Ehrmanntraut, Fabian Egidy, and Christian Glaßer

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
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 [P. Pudlák, 2017], which studies incompleteness in the finite domain and which mentions the construction of such oracles as open problem. The oracle shows that NP ∩ coNP is indispensable in the list of hypotheses studied by Pudlák. Hence one should consider stronger hypotheses, in order to find a universal one.
Cite as

Anton Ehrmanntraut, Fabian Egidy, and Christian Glaßer. Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ehrmanntraut_et_al:LIPIcs.MFCS.2022.45,
  author =	{Ehrmanntraut, Anton and Egidy, Fabian and Gla{\ss}er, Christian},
  title =	{{Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.45},
  URN =		{urn:nbn:de:0030-drops-168435},
  doi =		{10.4230/LIPIcs.MFCS.2022.45},
  annote =	{Keywords: computational complexity, promise classes, proof complexity, complete sets, oracle construction}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact