Complexity Hierarchies Beyond Elementary

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.

Version 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 (5)

• 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
• Non-Elementary Complexities for Branching VASS, MELL, and Extensions

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