A tutorial on enumeration complexity: defining traceability
Yann Strozecki9 juin 2022 - 14:00
We review the different ways tractability is defined in enumeration using as complexity measure total time, incremental time, delay and space. We present the associated complexity classes and show how they relate. The focus is on understanding incremental polynomial time and polynomial delay and the typical algorithms with this complexity. We also briefly present low complexity classes and some possible alternative to exhaustive enumeration.