Complexity Hierarchies Beyond Elementary
arXiv:1312.5686 · doi:10.1145/2858784
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.
arXiv commentVersion 3 is the published version in TOCT 8(1:3), 2016. I will keep updating the catalogue of problems from Section 6 in future revisions
References in corpus (11)
- On the decidability and complexity of Metric Temporal Logic over finite words
- Ackermannian and Primitive-Recursive Bounds with Dickson's Lemma
- Demystifying Reachability in Vector Addition Systems
- Multiply-Recursive Upper Bounds with Higman's Lemma
- The Power of Well-Structured Systems
- Alternating register automata on finite words and trees
- Graph Logics with Rational Relations
- The Power of Priority Channel Systems
- Non-Elementary Complexities for Branching VASS, MELL, and Extensions
- Relating timed and register automata
- The Parametric Ordinal-Recursive Complexity of Post Embedding Problems
Cited by in corpus (7)
- Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension
- Non-Elementary Complexities for Branching VASS, MELL, and Extensions
- Bisimulation Equivalence of First-Order Grammars is ACKERMANN-Complete
- Adding the Relation Meets to the Temporal Logic of Prefixes and Infixes makes it EXPSPACE-Complete
- Equivalence of pushdown automata via first-order grammars
- The Fluted Fragment with Transitive Relations
- The addition of temporal neighborhood makes the logic of prefixes and sub-intervals EXPSPACE-complete