Skip to Main content Skip to Navigation
New interface
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 metadata
Contributor : Sylvain Schmitz Connect in order to contact the contributor
Submitted on : Thursday, February 4, 2016 - 12:11:08 PM
Last modification on : Friday, July 8, 2022 - 10:08:01 AM

Links full text



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



Record views