Enumeration Classes Defined by Circuits

Nadia Creignou, Arnaud Durand, Heribert Vollmer

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 $\mathbf{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},
}
Figure