Details
| Original language | English |
|---|---|
| Title of host publication | 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022 |
| Editors | Stefan Szeider, Robert Ganian, Alexandra Silva |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| ISBN (electronic) | 9783959772563 |
| Publication status | Published - 22 Aug 2022 |
| Event | 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022 - Vienna, Austria Duration: 22 Aug 2022 → 26 Aug 2022 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 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.
Keywords
- Boolean circuit, Computational complexity, enumeration problem
ASJC Scopus subject areas
- Computer Science(all)
- Software
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022. ed. / Stefan Szeider; Robert Ganian; Alexandra Silva. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. 39 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 241).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › 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 -