Enumeration Classes Defined by Circuits

Publikation: Beitrag in Buch/Bericht/Sammelwerk/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Autoren

Externe Organisationen

  • Universite d'Aix-Marseille
  • Université de Paris
Forschungs-netzwerk anzeigen

Details

OriginalspracheEnglisch
Titel des Sammelwerks47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
Herausgeber/-innenStefan Szeider, Robert Ganian, Alexandra Silva
Herausgeber (Verlag)Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (elektronisch)9783959772563
PublikationsstatusVeröffentlicht - 22 Aug. 2022
Veranstaltung47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022 - Vienna, Österreich
Dauer: 22 Aug. 202226 Aug. 2022

Publikationsreihe

NameLeibniz International Proceedings in Informatics, LIPIcs
Band241
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

Zitieren

Enumeration Classes Defined by Circuits. / Creignou, Nadia; Durand, Arnaud; Vollmer, Heribert.
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/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Creignou, N, Durand, A & Vollmer, H 2022, Enumeration Classes Defined by Circuits. in S Szeider, R Ganian & A Silva (Hrsg.), 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022., 39, Leibniz International Proceedings in Informatics, LIPIcs, Bd. 241, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, Vienna, Österreich, 22 Aug. 2022. https://doi.org/10.48550/arXiv.2205.00539, https://doi.org/10.4230/LIPIcs.MFCS.2022.38
Creignou, N., Durand, A., & Vollmer, H. (2022). Enumeration Classes Defined by Circuits. In S. Szeider, R. Ganian, & A. Silva (Hrsg.), 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022 Artikel 39 (Leibniz International Proceedings in Informatics, LIPIcs; Band 241). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.48550/arXiv.2205.00539, https://doi.org/10.4230/LIPIcs.MFCS.2022.38
Creignou N, Durand A, Vollmer H. Enumeration Classes Defined by Circuits. in Szeider S, Ganian R, Silva A, Hrsg., 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2022. 39. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.48550/arXiv.2205.00539, 10.4230/LIPIcs.MFCS.2022.38
Creignou, Nadia ; Durand, Arnaud ; Vollmer, Heribert. / Enumeration Classes Defined by Circuits. 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. (Leibniz International Proceedings in Informatics, LIPIcs).
Download
@inproceedings{fb37b2b8ad974430af6d698c444777dd,
title = "Enumeration Classes Defined by Circuits",
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",
author = "Nadia Creignou and Arnaud Durand and Heribert Vollmer",
year = "2022",
month = aug,
day = "22",
doi = "10.48550/arXiv.2205.00539",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Stefan Szeider and Robert Ganian and Alexandra Silva",
booktitle = "47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022",
address = "Germany",
note = "47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022 ; Conference date: 22-08-2022 Through 26-08-2022",

}

Download

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 -

Von denselben Autoren