Complexity Hierarchies Beyond Elementary

Sylvain Schmitz

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.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment