Enumeration Classes Defined by Circuits
Open Access
- 28 November 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 17 (4) , 1-23
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
All Related Versions
This publication has 20 references indexed in Scilit:
- On Acyclic Conjunctive Queries and Constant Delay Enumeration2007
- Boolean Functions and Computation Models2002
- A Generalized Quantifier Concept in Computational Complexity Theory1999
- Introduction to Circuit Complexity1999
- On the Complexity of Dualization of Monotone Disjunctive Normal FormsJournal of Algorithms, 1996
- On uniformity within NC1Journal of Computer and System Sciences, 1990
- First-order definability on finite structuresAnnals of Pure and Applied Logic, 1989
- On generating all maximal independent setsInformation Processing Letters, 1988
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979