Incremental delay enumeration: Space and time

Abstract : We investigate the relationship between several enumeration complexity classes and focus in particular on problems having enumeration algorithms with incremental and polynomial delay ( IncP andDelayP respectively). We show that, for some algorithms, we can turn an average delay into a worst case delay without increasing the space complexity, suggesting that IncP1 = DelayP even with polynomially bounded space. We use the Exponential Time Hypothesis to exhibit a strict hierarchy inside IncP which gives the first separation of DelayP andIncP. Finally we relate the uniform generation of solutions to probabilistic enumeration algorithms with polynomial delay and polynomial space.
Complete list of metadatas

https://hal.inria.fr/hal-01923091
Contributor : Florent Capelli <>
Submitted on : Wednesday, November 14, 2018 - 10:30:52 PM
Last modification on : Friday, March 22, 2019 - 1:36:26 AM

Links full text

Identifiers

Citation

Florent Capelli, Yann Strozecki. Incremental delay enumeration: Space and time. Discrete Applied Mathematics, Elsevier, 2018, ⟨10.1016/j.dam.2018.06.038⟩. ⟨hal-01923091⟩

Share

Metrics

Record views

70