Details
Originalsprache | Englisch |
---|---|
Titel des Sammelwerks | 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022 |
Herausgeber/-innen | Stefan Szeider, Robert Ganian, Alexandra Silva |
Herausgeber (Verlag) | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
ISBN (elektronisch) | 9783959772563 |
Publikationsstatus | Veröffentlicht - 22 Aug. 2022 |
Veranstaltung | 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022 - Vienna, Österreich Dauer: 22 Aug. 2022 → 26 Aug. 2022 |
Publikationsreihe
Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Band | 241 |
ISSN (Print) | 1868-8969 |
Abstract
We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In this way we obtain a framework to distinguish between the complexity of different problems known to be in DelayP, for which a formal way of comparison was not possible to this day.
ASJC Scopus Sachgebiete
- Informatik (insg.)
- Software
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022. Hrsg. / Stefan Szeider; Robert Ganian; Alexandra Silva. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. 39 (Leibniz International Proceedings in Informatics, LIPIcs; Band 241).
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Aufsatz in Konferenzband › Forschung › Peer-Review
}
TY - GEN
T1 - Enumeration Classes Defined by Circuits
AU - Creignou, Nadia
AU - Durand, Arnaud
AU - Vollmer, Heribert
PY - 2022/8/22
Y1 - 2022/8/22
N2 - We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In this way we obtain a framework to distinguish between the complexity of different problems known to be in DelayP, for which a formal way of comparison was not possible to this day.
AB - We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In this way we obtain a framework to distinguish between the complexity of different problems known to be in DelayP, for which a formal way of comparison was not possible to this day.
KW - Boolean circuit
KW - Computational complexity
KW - enumeration problem
UR - http://www.scopus.com/inward/record.url?scp=85137555011&partnerID=8YFLogxK
U2 - 10.48550/arXiv.2205.00539
DO - 10.48550/arXiv.2205.00539
M3 - Conference contribution
AN - SCOPUS:85137555011
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
A2 - Szeider, Stefan
A2 - Ganian, Robert
A2 - Silva, Alexandra
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
Y2 - 22 August 2022 through 26 August 2022
ER -