Skip to Main content Skip to Navigation
Journal articles

Complexity Hierarchies Beyond Elementary

Sylvain Schmitz 1, 2
1 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], Inria Saclay - Ile de France
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, July 2, 2020 - 5:26:03 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