19 juin 2023
Arnaud Durand (IMJ-PRG)Enumerating is the task of generating one by one and without repetition the solutions of an algorithmic problem. Enumeration problems have deserved a lot of attention in the recent years in algorithms, complexity and databases.
In this talk we will first present an overview of the complexity landscape for enumeration problems. We will then introduce a different measure of complexity based on using Boolean circuits as enumerators. We will show that a lot of well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability can be considered under this angle. In this way we obtain a framework to distinguish between the complexity of different problems known to be in DelayP (the class of problems whose solutions can be enumerated with polynomial delay), for which a formal way of comparison was not possible until now.