2022/05/01 by Creignou, Nadia, Durand, Arnaud, Vollmer, Heribert
#Computation and Language (cs.CL) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.1.1 #F.1.3 #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2205.00539
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.