2013/12/31 by Sylvain Schmitz · 4 citations
Computer Science · #cs.CC #cs.LO
paper · pdf · doi:10.1145/2858784
published as ACM Transactions on Computation Theory vol. 8, number 1, article 3, 2016 · 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
arxiv created 2016/02/04 · arxiv updated 2016/02/05
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.