Skip to Main content Skip to Navigation
Journal articles

Incremental delay enumeration: Space and time

Abstract : We investigate the relationship between several enumeration complexity classes andfocus in particular on problems having enumeration algorithms with incremental andpolynomial delay ( IncP andDelayP respectively). We show that, for some algorithms, wecan 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 theExponential Time Hypothesis to exhibit a strict hierarchy inside IncP which gives the firstseparation of DelayP andIncP. Finally we relate the uniform generation of solutions toprobabilistic enumeration algorithms with polynomial delay and polynomial space.
Complete list of metadata

https://hal.inria.fr/hal-01923091
Contributor : Accord Elsevier CCSD Connect in order to contact the contributor
Submitted on : Tuesday, December 21, 2021 - 10:48:10 AM
Last modification on : Friday, July 8, 2022 - 10:06:24 AM
Long-term archiving on: : Wednesday, March 23, 2022 - 9:21:53 AM

File

S0166218X18304001.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial 4.0 International License

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

115

Files downloads

31