Nonelementary Problem¶

A decidable decision problem whose inherent worst-case resource needs exceed every fixed-height exponential-tower bound.

Version: v1 · 2026-10-07 · History
Domain-specific #: 13961
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Computational Complexity → Computer Science & Software Engineering
Aliases: Non-elementary problem

Core Idea¶

A nonelementary problem, as used here, is a decidable yes/no problem whose inherent worst-case resource requirement exceeds every fixed-height exponential-tower bound under a stated standard computation model and input encoding. An algorithm can still decide the problem; the distinction is that no correct decision procedure has an elementary upper bound. Even a very tall tower is elementary if its height is one fixed number independent of input size.[^{ref-3e11a12649d4][}ref-e7b3b8ae5413][^ref-8e925abebfbf]

Meyer's original report says that truth for weak monadic second-order logic of one successor (WS1S) is decidable but not elementary-recursive. Stockmeyer's original thesis establishes a nonelementary lower bound for equivalence of star-free expressions with complement. Schmitz later analyzes WS1S satisfiability and star-free equivalence at tower scale; that later formulation is kept distinct from Meyer's truth wording.[^{ref-3e11a12649d4][}ref-e7b3b8ae5413][^ref-8e925abebfbf]

Scope of Application¶

Meyer's case takes an encoded WS1S sentence over the successor structure and asks whether it is true. Stockmeyer's case takes two star-free expressions, formed with union, concatenation, and complement, and asks whether they denote the same language. They are unlike questions in logic and formal-language theory, yet both supply a decidable input family, an input-size measure, and a result beyond every fixed elementary tower.[^{ref-3e11a12649d4][}ref-e7b3b8ae5413][^ref-8e925abebfbf]

The formalism matters. Stockmeyer's thesis treats expressions with an explicit squaring operation separately; that is not the same syntax or lower-bound statement as star-free equivalence. Schmitz's fast-growing complexity classes can further locate particular nonelementary problems, but belonging to a specified F_alpha class or having a specific proof reduction is not required by this entry's identity.[^{ref-e7b3b8ae5413][}ref-8e925abebfbf]

Clarity¶

Fix the yes/no question, finite input encoding, computation model, and resource. Establish that some algorithm decides every input. Then ask whether any decision algorithm achieves an elementary worst-case bound. If one does, the problem is not nonelementary even when that bound is impractically large. A single slow implementation, one hard input, or hardness at just one fixed exponential level cannot establish the stronger claim.[^{ref-e7b3b8ae5413][}ref-8e925abebfbf]

An undecidable problem lacks a total decision algorithm and falls outside the decidable scope here. “Nonelementary” also does not imply that every particular input is slow. Stockmeyer frames lower-bound resources asymptotically over growing inputs; easy instances can coexist with the worst-case theorem.[^ref-e7b3b8ae5413]

Manages Complexity¶

The term marks the frontier between all fixed tower heights and growth requiring more than any one fixed height can provide. It prevents “very large” from standing in for a quantified complexity claim. WS1S makes the separate decidability point: an answer is computable in principle, yet an elementary resource bound is unavailable. Schmitz's hierarchy then distinguishes tower-scale cases from still faster decidable problems.[^{ref-3e11a12649d4][}ref-8e925abebfbf]

The resource-scaling skeleton belongs to live Complexity (Time/Space). This entry specializes it to a decidable decision problem with the beyond-elementary property; the problem is not itself a complexity class as a set of problems. The direct DAG edge therefore records strict composition/presupposes, not subsumption.[^ref-8e925abebfbf]

Abstract Reasoning¶

An algorithm with a tower bound of height seven still gives an elementary upper bound: seven is fixed. To establish nonelementarity for the problem, a lower-bound result must rule out every fixed height for all correct decision procedures under the same formulation. The number seven is illustrative, not a theorem about either example. If a later elementary algorithm solves that same question, an earlier claim based only on one slow implementation fails.[^{ref-e7b3b8ae5413][}ref-8e925abebfbf]

Knowledge Transfer¶

The two examples transfer the classification test, not each other's proof details. A formula-truth question and a language-equivalence question have different syntax and arguments, but each can be checked for decidability, explicit input size, and the all-fixed-heights lower bound. A new verification or automata question needs its own theorem; resemblance to WS1S or star-free syntax is not enough.[^{ref-3e11a12649d4][}ref-e7b3b8ae5413][^ref-8e925abebfbf]

Example¶

WS1S truth. The input is a weak monadic second-order sentence over the standard natural-number successor structure. Meyer reports decidability and non-elementary-recursiveness. The sentence fixes the yes/no problem; encoded formula length supplies size; the theorem places its worst-case decision resources beyond elementary bounds. This example is stated as truth, following the original report.[^ref-3e11a12649d4]

Star-free equivalence. The input is a pair of expressions using union, concatenation, and complement. The question is whether both denote the same language. Stockmeyer reports the equivalence problem as not elementary-recursive; Schmitz analyzes its tower-scale complexity. The pair's encoding supplies input size, and the problem-level lower bound supplies the differentia. Neither source here is used to claim that one small pair is hard.[^{ref-e7b3b8ae5413][}ref-8e925abebfbf]

Relationships to Other Abstractions¶

Current abstraction Nonelementary Problem Domain-specific

Parents (1) — more general patterns this builds on

Nonelementary Problem presupposes Complexity (Time/Space) Prime

The nonelementary classification presupposes a worst-case resource-scaling comparison over input size.

Hierarchy paths (5) — routes to 4 parentless roots

Nonelementary Problem → Complexity (Time/Space) → Asymptotic Behavior → Approximation → Representation → Abstraction

Show alternative paths (4)

Neighborhood in Abstraction Space¶

Nonelementary Problem sits in a sparse region of the domain-specific corpus (86^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Computational Complexity & Hardness (17 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

A fixed-height tower, regardless of height, remains elementary. One inefficient algorithm does not prove a problem nonelementary. An undecidable problem is outside the admitted decidable class. Stockmeyer's separate squaring-expression problem is not the star-free equivalence example. Meyer's WS1S truth and Schmitz's WS1S satisfiability are identified separately rather than quoted as identical source statements.[^{ref-3e11a12649d4][}ref-e7b3b8ae5413][^ref-8e925abebfbf]

References¶

[^ref-3e11a12649d4]: Albert R. Meyer, Weak Monadic Second Order Theory of Successor is not Elementary-recursive, MIT-LCS-TM-038, December 1973. MIT institutional record and original-report abstract state WS1S truth decidability and non-elementarity. Scanned full report; the proof pages were not independently inspected.

[^ref-e7b3b8ae5413]: Larry J. Stockmeyer, The Complexity of Decision Problems in Automata Theory and Logic, MIT PhD thesis, 1974, abstract and printed p.69 on star-free-expression equivalence; §4.1 treats squaring expressions separately. The original thesis distinguishes its nonelementary equivalence result from fixed-level squaring bounds.

[^ref-8e925abebfbf]: Sylvain Schmitz, Complexity Hierarchies Beyond Elementary, original research preprint, 2013, Introduction pp.1–2; §2.2.4–§2.2.5; §3.1. It describes WS1S satisfiability and star-free-expression equivalence as nonelementary and introduces a finer hierarchy, with Tower as a class between elementary and primitive-recursive.