COMPLEXITY HIERARCHIES BEYOND ELEMENTARY
Sylvain Schmitz · 2015
Abstract. We introduce a hierarchy of fast-growing complexity classes and show its suitability for completeness statements of many non ele-mentary problems. This hierarchy allows the classification of many deci-sion problems with a non-elementary complexity, which occur naturally in logic, combinatorics, formal languages, verification, etc., with com-plexities ranging from simple towers of exponentials to Ackermannian and beyond. 1.