Séminaire Algorithmique : « Enumeration Classes Defined by Circuits », Arnaud Durand (IMJ, Univ. Paris-Diderot)

Enumerating is the task of generating all solutions associated with an instance of a computational problem. 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 (conditionally but also unconditionally) between the complexity of different problems known to be computable with polynomial delay, for which a formal way of comparison was not possible to this day. The approach offers a different measure of efficient enumeration such as the one defined using Constant Delay in the context of enumeration for query answering.

Joint work with Nadia Creignou and Heribert Vollmer.