Enumeration Classes Defined by Circuits
This provides a formal framework for comparing complexities of enumeration problems, addressing a gap in computational complexity theory.
The paper tackles the problem of distinguishing complexity among enumeration problems within DelayP by introducing new classes defined via Boolean circuits, and it successfully locates several known problems like graph theory and SAT enumeration within these classes.
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.