Source-linked AI summary
Complexity Hierarchies Beyond Elementary
Sylvain Schmitz
TL;DR
Many natural decision problems have non-elementary complexity, but classical hierarchies lack sufficiently precise intermediate classes for them. The paper defines an ordinal-indexed fast-growing hierarchy with tailored complexity classes and completeness notions, showing landmarks such as Tower = F3 and using the framework across examples including lossy counter systems. Its scope remains limited because no sensible ordinal-indexed hierarchy can exhaust Recursive complexity.
Problem
Classical complexity hierarchies provide too few suitable intermediate classes for natural non-elementary decision problems arising in areas such as logic, formal languages, and verification.
Method
The paper defines fast-growing classes Fα using a single Fα time bound composed with functions from lower levels, enabling reductions and completeness statements.
Results
The hierarchy captures landmarks including Tower = F3 and supports completeness-based classifications for non-elementary problems.
Takeaways & Limitations
The framework provides more precise terminology for comparing and classifying high-complexity decision problems than ad hoc complexity descriptions.
Takeaways & Limitations
The hierarchy is intended to classify naturally occurring classes above Elementary, not to exhaust Recursive complexity using sensible ordinal notations.
Abstract
from arXiv · showhide
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.
1. Introduction
Many natural decision problems lie beyond Elementary, yet classical complexity hierarchies provide too few intermediate classes to classify them precisely. The paper proposes an ordinal-indexed fast-growing hierarchy designed to support completeness statements for such problems, while acknowledging that it cannot exhaust Recursive complexity.
- Non Elementary Problems.: Classical hierarchies leave a gap between Elementary and Primitive-Recursive, where problems such as WS1S and SFEq naturally belong.These problems are non-elementary but not hard for Primitive-Recursive under reasonable reductions.
- Non Elementary Problems.: The paper motivates finer classifications because non-elementary problems occur widely in logic, combinatorics, formal languages, verification, and practical tools such as MONA.Complexity distinctions can also guide the search for practically relevant restrictions.
- Our Contribution.: The paper proposes an ordinal-indexed hierarchy (Fα)α of fast-growing complexity classes for non-elementary complexities.The hierarchy includes Tower-like, non-primitive-recursive, Ackermannian, and higher classes.
- Our Contribution.: The hierarchy aims to replace coarse membership and non-membership statements with precise completeness classifications.The authors suggest that statements placing a problem in Fα but no lower Fβ can often be sharpened to Fα-completeness.
- Our Contribution.: The approach is deliberately limited: no sensible ordinal-indexed hierarchy can exhaust Recursive complexity.The paper therefore focuses on definitions from below for naturally occurring classes above Elementary.
2. Fast-Growing Complexity Classes
The paper defines ordinal-indexed fast-growing complexity classes using a single application of Fα after a lower-level preprocessing function, providing finer classifications for non-elementary problems. The hierarchy fills gaps such as Tower between Elem and PR and extends through Ackermannian and higher classes.
- Class definition: Each Fα class consists of problems decidable within time bounded by one application of Fα composed with a function from lower levels Fβ, β < α.This avoids the arbitrary finite compositions allowed in the corresponding function classes.
- Growth hierarchy: The ordinal-indexed function hierarchy includes elementary, primitive-recursive, multiply-recursive, Ackermannian, hyper-Ackermannian, and higher growth milestones.Examples include Fω for Ackermannian growth, Fωω for hyper-Ackermannian growth, and Fε0 beyond provable totality in Peano arithmetic.
- Reduction classes: The hierarchy introduces smaller classes by restricting reductions to lower-level functions, rather than allowing repeated applications of the target fast-growing function.For α ≥ 3, deterministic time, nondeterministic time, and space formulations are equivalent according to the cited lemma.
- Motivation: The hierarchy addresses missing intermediate complexity classes because Elem is too small for problems such as WS1S and SFEq, while PR is too large.The proposed Tower class is defined as F3 and is closed under elementary reductions.
- Completeness: The classes are intended to support completeness statements for natural decision problems, with Fα-TM and Fα-MM given as basic Fα-complete problems.The paper also presents a catalogue of natural complete problems for Fω and higher classes.
3. Fast-Growing Complexities in Action
The paper illustrates its fast-growing complexity hierarchy through star-free-expression equivalence and lossy-counter-machine reachability, showing how automata and well-quasi-order methods support Tower and Ackermannian classifications.
- 3.1. A Tower-Complete Example: SFEq is Tower-hard under elementary reductions and belongs to Tower via automata constructions whose complement handling causes exponential blowups.The same automata-based approach yields the upper bound for WS1S.
- 3.1.2. Discussion: Tower is a suitable intermediate class because Elementary is strictly below Tower, while common k-ExpTime lower bounds can yield Tower-hardness when uniform over infinitely many k.The literature’s E4 notation is too coarse because it contains all finite iterates of the tower function.
- 3.2. Lossy Counter Systems: Lossy-counter-machine reachability is Ack-hard, with Ack defined as problems decidable using Fω resources after primitive-recursive input preprocessing.The problem asks whether a target configuration is reachable from the initial configuration.
- 3.2.1. Decidability of LCM: The LCM algorithm searches backward through minimal witnesses, whose configuration ordering forms bad sequences controlled by successor growth.Well-quasi-ordering ensures finite branching and finite height, making the search finite.
- 3.2.2. Length Function Theorems: A length-function bound limits shortest witnesses, enabling nondeterministic exploration that aborts after the bound and runs within primitive-recursive variants of Fh,ω.The resulting overall bound is Fh,ω(p(n)) for primitive-recursive h and p, placing LCM in Ack.
- 3.2.4. Discussion: The paper notes that some very tight complexity classes are inconvenient because they are not robust across computation models or are not closed under reductions.These limitations motivate using broader, reduction-closed classes for completeness statements.
4. Robustness
The hierarchy is robust to alternative fast-growing functions, resource bounds, computation models, and reduction types. Technical results show that these variants preserve the intended complexity classes up to controlled ordinal shifts.
- Robustness results: Using the tower function instead of F3 and a relativised Fω for applications leaves the resulting classifications unchanged under the proved robustness results.The paper explicitly uses these substitutions for lower and upper bounds in SFEq, WS1S, and LCM.
- Relativised hierarchies: Alternative generative functions define the same classes up to inclusions, with relativised variants requiring an ordinal-index offset.For strictly increasing primitive-recursive h and α ≥ω, the relativised class Fh,α equals Fα.
- Machine and resource models: For α ≥3, Fα is robust to switching between time and space bounds, machine models, and deterministic, nondeterministic, or alternating computation.This follows from closure under composition with reductions in F<α.
- Reductions: Each Fα is closed under many-one and, for α ≥3, Turing reductions computed within F<α.Thus reducing a language to a problem in Fα preserves membership in Fα.
5. Strictness
The paper establishes that the fast-growing hierarchy is strict and that its functions are effectively constructible within elementary overhead. It also identifies special behavior at low levels and boundaries on how far ordinal-indexed hierarchies can extend.
- Constructibility: Every Fα function is elementarily constructible when its base function is elementary constructible.Theorem 5.1 gives this for relativised functions Fh,α and hence for the standard hierarchy.
- Strictness: For all c > 0 and 2 ≤β < α, the classes defined with bounded compositions are strictly separated.The separation is established by diagonalisation languages that belong to the higher class but not the lower one.
- Consequences: Strictness yields characterisations of primitive-recursive and multiply-recursive problems and rules out complete problems for certain union classes under F<α reductions.The absence of such complete problems follows because completeness would collapse distinct hierarchy levels.
- Low levels: F1 contains exactly linear functions, while F2 corresponds to weak, or linear, exponential-time complexity.The paper states F2(n) = 2n+1+log(n+1) −1 and places it in 2O(n).
6. A Short Catalogue
The catalogue applies the hierarchy to decision problems from verification, formal languages, logic, timed systems, and data systems. These examples span Tower, Ackermannian, and higher levels, with bounds often derived from well-quasi-ordering arguments.
- Non-primitive-recursive levels: Known problems are classified at levels including Fω, Fωω, Fωωω, and Fε0, extending beyond the familiar Tower level.The catalogue includes reachability, universality, satisfiability, and termination-style problems across several formalisms.
- Proof patterns: The catalogue connects upper bounds to well-quasi-orders and matching length-function theorems, while lower bounds commonly come from bounded-machine halting problems.This pattern recurs across lossy or insertion channels, counter systems, Petri-net variants, and timed models.
- Ackermannian problems: Ack-complete examples include vector addition systems, channel systems, relevant implication, timed automata, and related verification problems.The listed lower and upper bounds use reductions and length-function theorems for systems such as Dickson’s Lemma.
- Beyond Ackermannian complexity: Higher classifications include Fωω-complete graph-database queries and Fε0-complete finite satisfiability for attributed data words.The catalogue also records Fωω-hardness for enriched systems and database queries.
7. Concluding Remarks
The proposed hierarchy supplies usable completeness classes for many non-elementary problems and links their complexity to ordinal-indexed well-quasi-order phenomena. Its coverage remains incomplete because natural problems at intermediate levels are not yet known.
- Contribution: The hierarchy identifies Tower = F3, Ack = Fω, and HAck = Fωω while supporting standard reductions and completeness statements.Its classes are close enough to the extended Grzegorczyk hierarchy to refine many complexity statements.
- Interpretation: Fα-completeness signals reliance on well-quasi-orders with maximal order type ωα, whose length-function theorems yield the corresponding bounds.This interpretation applies to the problems catalogued in Section 6.
- Open directions: No natural problems are currently known at some intermediate levels, including between Elem and Ack or between Ack and HAck.Parametric LCM and LCS are suggested candidates, but their known lower and upper bounds do not match.
Appendix A. Subrecursive Hierarchies
Appendix A supplies technical background and proofs omitted from the main text, including the inductive definition of Hardy functions controlled by a strictly increasing function.
- The appendix presents technical background and proofs missing from the main text.
- The Hardy-function construction is given as part of the appendix’s technical treatment of subrecursive hierarchies.
- Hardy functions hα are defined for ordinals α<ε0 using a strictly increasing control function h.
A.1. Hardy Functions.
The Hardy-function section develops transfinite iteration, monotonicity properties, and composition identities while identifying limitations of ordinal-indexed comparisons.
- The predecessor construction recursively follows fundamental sequences until reaching a successor ordinal, simplifying the definition of Hardy functions.
- Hardy functions generalize finite iteration by using transfinite iteration and diagonalisation at limit ordinals.For finite k, h_k(x) is the kth iterate of h.
- Hardy functions are expansive and monotone in both the base function and argument, but not necessarily monotone in the ordinal index.
- Transfinite induction establishes identities that support the Hardy-function framework and imply expansiveness and monotonicity of fast-growing functions.
- Composition can be internalised in the ordinal index only when ordinal addition agrees with natural sum, so the identity fails for some set-theoretic ordinal indices.The example H1(Hω(x)) demonstrates the failure when 1 + ω = ω but the corresponding Hardy-function composition is larger.
A.2. Monotonicity.
The monotonicity section refines ordinal comparison pointwise and uses ordinal norms to obtain eventual monotonicity of Hardy functions.
- The relations ≺x form a strict hierarchy of refinements between increasingly precise pointwise comparisons and the ordinal ordering.
- The norm Nβ supplies a threshold: whenever β < α and x ≥ Nβ, the pointwise ordering yields Hβ(x) ≤ Hα(x).
- Although ordinal-indexed hierarchies need not be pointwise monotone, β < α implies Hβ(x) ≤ Hα(x) for all sufficiently large x.
- The section also introduces the Ackermann hierarchy as a separate function hierarchy whose proofs require properties of its less uniform definition.
A.3. Ackermann Functions.
The Ackermann-function section proves basic expansiveness and monotonicity properties and establishes a tight comparison between Ackermann and fast-growing functions.
- The Ackermann hierarchy is less uniform than the fast-growing and Hardy hierarchies, making its basic proofs more involved.
- For α > 1, Ackermann functions are strictly expansive, strictly increasing in their argument, and pointwise monotone under the refined ordinal ordering.
- The proofs establish the Ackermann properties by simultaneous transfinite induction over the ordinal index.
- Aα(x) ≤ Fα(x) ≤ Aα(6x + 5) for every α > 0 and x, relating the Ackermann and fast-growing hierarchies.
- The comparison theorem is proved by transfinite induction over α, with separate base, successor, and limit cases.
A.4. Relativised Functions.
Lemma A.5 bounds relativised fast-growing functions when h is eventually dominated by F_β, yielding a shifted-index bound with γ below β + α.
- Lemma A.5: If h(x) ≤ F_β(x) for all x ≥ x0, then F_{h,α}(x) ≤ F_{β+α}(F_γ(x)) for all x ≥ x0.The constructed ordinal γ satisfies γ < β + α whenever β + α > 0.
- Ordinal decomposition: The proof decomposes β into Cantor normal form, separating an initial segment β′ from the remainder γ so that β = β′ + γ and β + α = β′ + α.This decomposition also establishes the required bound on γ.
- Inductive proof: A simple induction over α first derives F_{h,α}(x) ≤ F_{F_β,α}(x), which supports the final relativised bound.The induction includes base, successor, and limit-style steps in the displayed proof sequence.
A.5. Non-standard Assignment of Fundamental Sequences.
The section establishes bounds for fast-growing functions under monotone assignments of fundamental sequences, distinguishing strictly expansive assignments from all other monotone assignments.
- Section purpose: The section supplies technical details for the proof of Theorem 4.4 and identifies Lemma 4.6 as its immediate technical target.The section explicitly states both its theorem-proof and lemma-proof purposes.
- Lemma A.6: For monotone s, strictly expansive assignments satisfy F_{α,s} ≤ F_{s,α} ◦ s, while otherwise F_{α,s} ≤ F_α.The strictly expansive case is proved by transfinite induction over α.
- Proof strategy: The proof handles zero, successor, and limit ordinals separately, using monotonicity and induction hypotheses to propagate the comparison.At limit stages, the argument compares the assigned fundamental sequences at x and s(x).
A.6. Composing Hardy Functions.
The section develops composition and computation tools for Hardy functions, including a closure-style composition bound and an explicit procedure whose length and representation costs are controlled by associated hierarchies.
- Composition: For f ∈ F_<α, there exists g ∈ F_<α such that f ◦ F_α ≤ F_α ◦ g.The proof bounds f by a lower-level function and uses Hardy-function composition identities.
- Hardy computations: A Hardy computation is a terminating sequence of ordinal-number pairs preserving h^α_i(n_i) = h^α(n), with increasing numeric components and decreasing ordinal components.Termination follows from the monotonicity of h and the decreasing ordinal indices.
- Computational complexity: Each computation step updates the ordinal representation and numeric component, with costs bounded by p(G_α(h_α(n))) and e(h_α(n)), respectively.The bounds use the slow-growing hierarchy to control ordinal-term sizes and monotonicity to bound numeric updates.
- Length hierarchy: The length hierarchy measures computation length, with ℓ = h_α(n) and h_ℓ(n) = h_α(n).This identity connects the number of computation steps with the value of the Hardy function.
- Representation bounds: The slow-growing function G_α(x) is obtained by replacing each occurrence of ω in α’s Cantor normal form with x + 1, and it bounds the sizes of intermediate ordinal terms.The size bound is stated for every ordinal in a Hardy computation when n > 0.
- Zero-input boundary: The restriction n > 0 is handled separately: either h(0) = 0, or computation can begin from a reduced ordinal after applying h(0).This gives a case-based way to accommodate zero inputs.