# Complexity Hierarchies Beyond Elementary

arXiv: https://arxiv.org/abs/1312.5686 · HTML: https://mlsanity.com/paper/1312.5686/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Dec 2013.

## Built on by (most cited first, 2 of 2)

- [Improved Ackermannian lower bound for the Petri nets reachability problem](https://mlsanity.com/paper/2105.08551/) (2021)
- [Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster](https://mlsanity.com/paper/2407.20822/) (2024)

## Abstract (arXiv)

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.