Paper ID: 2205.00539

Enumeration Classes Defined by Circuits

Nadia Creignou, Arnaud Durand, Heribert Vollmer

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.

Submitted: May 1, 2022