Complexity Hierarchies Beyond Elementary

Sylvain Schmitz 1, 2
1 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : We introduce a hierarchy of fast-growing complexity classes and show its suitability for completeness statements of many non elementary problems. This hierarchy allows the classification of many decision problems with a non-elementary complexity, which occur naturally in logic, combinatorics, formal languages, verification, etc., with complexities ranging from simple towers of exponentials to Ackermannian and beyond.
Type de document :
Article dans une revue
ACM Transactions on Computation Theory, ACM, 2016, 8 (1), 〈10.1145/2858784〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01267354
Contributeur : Sylvain Schmitz <>
Soumis le : jeudi 4 février 2016 - 12:11:08
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14

Lien texte intégral

Identifiants

Citation

Sylvain Schmitz. Complexity Hierarchies Beyond Elementary. ACM Transactions on Computation Theory, ACM, 2016, 8 (1), 〈10.1145/2858784〉. 〈hal-01267354〉

Partager

Métriques

Consultations de la notice

138