Enumeration Classes Defined by Circuits
Lists
Only you see this
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.
BibTeX
@article{creignou2022enumeration,
author = {Nadia Creignou and Arnaud Durand and Heribert Vollmer},
title = {{Enumeration Classes Defined by Circuits}},
journal = {ACM Trans. Comput. Theory},
year = {2022},
}| On the Complexity of Hard Enumeration Problems | arXiv · 2016 |
| A Circuit-Based Approach to Efficient Enumeration | arXiv · 2017 |
| Paradigms for Parameterized Enumeration | arXiv · 2013 |
| Enumerating Homomorphisms | arXiv · 2009 |
| Complexity classifications for different equivalence and audit problems for Boolean circuits | Logical · 2012 |
| Parameterized Enumeration with Ordering | arXiv · 2013 |