Incremental delay enumeration: Space and time

Capelli, Florent; Strozecki, Yann

Document type :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1016/j.dam.2018.06.038

Title :

Incremental delay enumeration: Space and time

Author(s) :

Capelli, Florent [Auteur]

Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Linking Dynamic Data [LINKS]
Strozecki, Yann [Auteur]
Données et algorithmes pour une ville intelligente et durable - DAVID [DAVID]

Journal title :

Discrete Applied Mathematics

Publisher :

Elsevier

Publication date :

2018-08

ISSN :

0166-218X

English keyword(s) :

Enumeration
Incremental time
Polynomial delay
Structural complexity
Exponential time hypothesis

HAL domain(s) :

Informatique [cs]
Informatique [cs]/Complexité [cs.CC]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Popular science :

Non

ANR Project :

Requêtes d'Agrégation

Collections :