Search Results

Documents authored by Egidy, Fabian

Document
DOI: 10.4230/LIPIcs.MFCS.2025.43
The Complexity of Computing Second Solutions

Authors: Fabian Egidy, Christian Glaßer, and Fynn Godau

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We study the complexity of computing second solutions for NP search problems, i. e., given a problem instance x and a valid solution y, we have to find another valid solution y'. Our main result shows that for typical NP decision problems, the complexity of computing second solutions is completely determined by the choice of the type of solution (i. e., the specific function problem), but independent of the underlying decision problem. More precisely, we show that for every X ∈ NP that is 1-paddable (a weak form of paddability), different choices of the type of solution lead to different second solution problems, which altogether have the same degree structure as the entire class of NP search problems (FNP). In fact, each degree of difficulty within FNP does occur as a second solution problem for X. This proves that typical NP decision problems have no intrinsic complexity w. r. t. the search for a second solution, but only the specification of the type of solution determines this complexity. This explains the empirical observation that the difficulty of computing second solutions strongly depends on the formulation of the problem. Moreover, we show that the complexities of a search problem and its second solution variant are independent in the following sense: For all search problems A and B representing two degrees of difficulty, there exists a search problem C such that 1) C is as difficult as A and 2) computing second solutions for C is as difficult as B.
Cite as

Fabian Egidy, Christian Glaßer, and Fynn Godau. The Complexity of Computing Second Solutions. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{egidy_et_al:LIPIcs.MFCS.2025.43,
  author =	{Egidy, Fabian and Gla{\ss}er, Christian and Godau, Fynn},
  title =	{{The Complexity of Computing Second Solutions}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.43},
  URN =		{urn:nbn:de:0030-drops-241505},
  doi =		{10.4230/LIPIcs.MFCS.2025.43},
  annote =	{Keywords: function problems, another solution problem, turing machines}
}
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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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