Search Results

Documents authored by Glaßer, Christian

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}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.9
NP-Completeness, Proof Systems, and Disjoint NP-Pairs

Authors: Titus Dose and Christian Glaßer

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
The article investigates the relation between three well-known hypotheses. - H_{union}: the union of disjoint ≤^p_m-complete sets for NP is ≤^p_m-complete - H_{opps}: there exist optimal propositional proof systems - H_{cpair}: there exist ≤^{pp}_m-complete disjoint NP-pairs The following results are obtained: - The hypotheses are pairwise independent under relativizable proofs, except for the known implication H_{opps} ⇒ H_{cpair}. - An answer to Pudlák’s question for an oracle relative to which ¬H_{cpair}, ¬H_{opps}, and UP has ≤^p_m-complete sets. - The converse of Köbler, Messner, and Torán’s implication NEE ∩ TALLY ⊆ coNEE ⇒ H_{opps} fails relative to an oracle, where NEE =^{df} NTIME(2^O(2ⁿ)). - New characterizations of H_{union} and two variants in terms of coNP-completeness and p-producibility of the set of hard formulas of propositional proof systems.
Cite as

Titus Dose and Christian Glaßer. NP-Completeness, Proof Systems, and Disjoint NP-Pairs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dose_et_al:LIPIcs.STACS.2020.9,
  author =	{Dose, Titus and Gla{\ss}er, Christian},
  title =	{{NP-Completeness, Proof Systems, and Disjoint NP-Pairs}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.9},
  URN =		{urn:nbn:de:0030-drops-118707},
  doi =		{10.4230/LIPIcs.STACS.2020.9},
  annote =	{Keywords: NP-complete, propositional proof system, disjoint NP-pair, oracle}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.33
Emptiness Problems for Integer Circuits

Authors: Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, and Marc Technau

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, addition, and multiplication is allowed turns out to be equivalent to the complement of polynomial identity testing (PIT). Our results imply the following improvements and insights on problems studied in earlier papers. We improve the bounds for the membership problem MC(\cup,\cap,¯,+,×) studied by McKenzie and Wagner 2007 and for the equivalence problem EQ(\cup,\cap,¯,+,×) studied by Glaßer et al. 2010. Moreover, it turns out that the following problems are equivalent to PIT, which shows that the challenge to improve their bounds is just a reformulation of a major open problem in algebraic computing complexity: 1. membership problem MC(\cap,+,×) studied by McKenzie and Wagner 2007 2. integer membership problems MC_Z(+,×), MC_Z(\cap,+,×) studied by Travers 2006 3. equivalence problem EQ(+,×) studied by Glaßer et al. 2010
Cite as

Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, and Marc Technau. Emptiness Problems for Integer Circuits. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{barth_et_al:LIPIcs.MFCS.2017.33,
  author =	{Barth, Dominik and Beck, Moritz and Dose, Titus and Gla{\ss}er, Christian and Michler, Larissa and Technau, Marc},
  title =	{{Emptiness Problems for Integer Circuits}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.33},
  URN =		{urn:nbn:de:0030-drops-80641},
  doi =		{10.4230/LIPIcs.MFCS.2017.33},
  annote =	{Keywords: computational complexity, integer expressions, integer circuits, polynomial identity testing}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2011.55
Applications of Discrepancy Theory in Multiobjective Approximation

Authors: Christian Glaßer, Christian Reitwießner, and Maximilian Witek

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract
We apply a multi-color extension of the Beck-Fiala theorem to show that the multiobjective maximum traveling salesman problem is randomized 1/2-approximable on directed graphs and randomized 2/3-approximable on undirected graphs. Using the same technique we show that the multiobjective maximum satisfiablilty problem is 1/2-approximable.
Cite as

Christian Glaßer, Christian Reitwießner, and Maximilian Witek. Applications of Discrepancy Theory in Multiobjective Approximation. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 55-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{glaer_et_al:LIPIcs.FSTTCS.2011.55,
  author =	{Gla{\ss}er, Christian and Reitwie{\ss}ner, Christian and Witek, Maximilian},
  title =	{{Applications of Discrepancy Theory in Multiobjective Approximation}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{55--65},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.55},
  URN =		{urn:nbn:de:0030-drops-33233},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.55},
  annote =	{Keywords: Discrepancy Theory, Multiobjective Optimization, Satisfiability, Traveling Salesman}
}
Document
DOI: 10.4230/DagSemProc.10501.1
10501 Abstracts Collection – Advances and Applications of Automata on Words and Trees

Authors: Christian Glasser, Jean-Eric Pin, Nicole Schweikardt, Victor Selivanov, and Wolfgang Thomas

Published in: Dagstuhl Seminar Proceedings, Volume 10501, Advances and Applications of Automata on Words and Trees (2011)

Abstract
From 12.12.2010 to 17.12.2010, the Dagstuhl Seminar 10501 ``Advances and Applications of Automata on Words and Trees'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Christian Glasser, Jean-Eric Pin, Nicole Schweikardt, Victor Selivanov, and Wolfgang Thomas. 10501 Abstracts Collection – Advances and Applications of Automata on Words and Trees. In Advances and Applications of Automata on Words and Trees. Dagstuhl Seminar Proceedings, Volume 10501, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{glasser_et_al:DagSemProc.10501.1,
  author =	{Glasser, Christian and Pin, Jean-Eric and Schweikardt, Nicole and Selivanov, Victor and Thomas, Wolfgang},
  title =	{{10501 Abstracts Collection – Advances and Applications of Automata on Words and Trees}},
  booktitle =	{Advances and Applications of Automata on Words and Trees},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10501},
  editor =	{Christian Glasser and Jean-Eric Pin and Nicole Schweikardt and Victor Selivanov and Wolfgang Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10501.1},
  URN =		{urn:nbn:de:0030-drops-31486},
  doi =		{10.4230/DagSemProc.10501.1},
  annote =	{Keywords: Automata theory, logic, verification, data structures, algorithms, complexity, games, infinite games with perfect information, reactive systems, specification and verification, combinatorics, hierarchies and reducibilities}
}
Document
DOI: 10.4230/DagSemProc.10501.2
10501 Executive Summary – Advances and Applications of Automata on Words and Trees

Authors: Christian Glasser, Jean-Eric Pin, Nicole Schweikardt, Victor Selivanov, and Wolfgang Thomas

Published in: Dagstuhl Seminar Proceedings, Volume 10501, Advances and Applications of Automata on Words and Trees (2011)

Abstract
The aim of the seminar was to discuss and systematize the recent fast progress in automata theory and to identify important directions for future research. For this, the seminar brought together more than 40 researchers from automata theory and related fields of applications. We had 19 talks of 30 minutes and 5 one-hour lectures leaving ample room for discussions. In the following we describe the topics in more detail.
Cite as

Christian Glasser, Jean-Eric Pin, Nicole Schweikardt, Victor Selivanov, and Wolfgang Thomas. 10501 Executive Summary – Advances and Applications of Automata on Words and Trees. In Advances and Applications of Automata on Words and Trees. Dagstuhl Seminar Proceedings, Volume 10501, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{glasser_et_al:DagSemProc.10501.2,
  author =	{Glasser, Christian and Pin, Jean-Eric and Schweikardt, Nicole and Selivanov, Victor and Thomas, Wolfgang},
  title =	{{10501 Executive Summary – Advances and Applications of Automata on Words and Trees}},
  booktitle =	{Advances and Applications of Automata on Words and Trees},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10501},
  editor =	{Christian Glasser and Jean-Eric Pin and Nicole Schweikardt and Victor Selivanov and Wolfgang Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10501.2},
  URN =		{urn:nbn:de:0030-drops-31474},
  doi =		{10.4230/DagSemProc.10501.2},
  annote =	{Keywords: Infinite games with perfect information, reactive systems, specification and verification, combinatorics, hierarchies and reducibilities}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1355
Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

Authors: Christian Glasser, Heinz Schmitz, and Victor Selivanov

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results: - The classes of the Boolean hierarchy over level $Sigma_1$ of the dot-depth hierarchy are decidable in $NL$ (previously only the decidability was known). The same remains true if predicates mod $d$ for fixed $d$ are allowed. - If modular predicates for arbitrary $d$ are allowed, then the classes of the Boolean hierarchy over level $Sigma_1$ are decidable. - For the restricted case of a two-letter alphabet, the classes of the Boolean hierarchy over level $Sigma_2$ of the Straubing-Th{'\e}rien hierarchy are decidable in $NL$. This is the first decidability result for this hierarchy. - The membership problems for all mentioned Boolean-hierarchy classes are logspace many-one hard for $NL$. - The membership problems for quasi-aperiodic languages and for $d$-quasi-aperiodic languages are logspace many-one complete for $PSPACE$.
Cite as

Christian Glasser, Heinz Schmitz, and Victor Selivanov. Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 337-348, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{glasser_et_al:LIPIcs.STACS.2008.1355,
  author =	{Glasser, Christian and Schmitz, Heinz and Selivanov, Victor},
  title =	{{Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{337--348},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1355},
  URN =		{urn:nbn:de:0030-drops-13554},
  doi =		{10.4230/LIPIcs.STACS.2008.1355},
  annote =	{Keywords: Automata and formal languages, computational complexity, dot-depth hierarchy, Boolean hierarchy, decidability, efficient algorithms}
}
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