Complexity Hierarchies Beyond Elementary

Sylvain Schmitz 1, 2
1 DAHU - Verification in databases
CNRS - Centre National de la Recherche Scientifique : UMR8643, Inria Saclay - Ile de France, ENS Cachan - École normale supérieure - Cachan, LSV - Laboratoire Spécification et Vérification [Cachan]
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.
Complete list of metadatas
Contributor : Sylvain Schmitz <>
Submitted on : Thursday, February 4, 2016 - 12:11:08 PM
Last modification on : Thursday, February 7, 2019 - 5:29:24 PM

Links full text



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



Record views