|
Enumeration Classes Defined by Circuits| title | Enumeration Classes Defined by Circuits |
|---|
| start_date | 2025/02/25 |
|---|
| schedule | 10h45 |
|---|
| online | no |
|---|
| location_info | salle S3 351, 3e étage |
|---|
| summary | 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. |
|---|
| responsibles | Grandjean |
|---|
Workflow history| from state (1) | to state | comment | date |
|---|
| submitted | published | | 2025/02/25 10:20 UTC |
| |
|