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, in the scope of this entry, is a decidable decision problem for which no correct decision algorithm has a worst-case elementary resource bound under the stated standard computation model and input encoding. “Elementary” permits an exponential tower of any fixed height, with a suitable ordinary base-level size function; the height must not grow with the input. A high but fixed tower remains elementary. The nonelementary claim is about the problem's inherent worst-case growth over input sizes, rather than a large runtime observed for one algorithm or input.^[1]^[2]^[3]

Two historically distinct cases make the boundary concrete. Meyer reports that truth in weak monadic second-order logic of one successor (WS1S) is decidable yet not elementary-recursive. Stockmeyer proves a nonelementary lower bound for equivalence of star-free expressions using complement. Schmitz later analyzes WS1S satisfiability and star-free-expression equivalence at tower scale. Meyer's truth formulation and Schmitz's satisfiability formulation should be identified by their sources rather than silently interchanged.^[1]^[2]^[3]

Structural Signature¶

Signature: fixed decidable yes/no question and encoding → input-size resource measure → every fixed elementary-tower bound is insufficient for every correct decision procedure.

Decision problem and decidability. A specified family of finite encoded inputs has a yes/no answer and a terminating decision procedure. Without a fixed question, there is no problem to classify; without decidability, the example belongs outside this entry's admitted scope.^[1]^[2]
Input-size and model frame. The worst-case resource is measured as the encoded input grows under a stated standard model. A formula or pair of expressions is an input; a single hard formula is not itself a nonelementary decision problem.^[2]^[3]
Elementary frontier. For any fixed finite tower height, one may choose that height once as part of a proposed bound. The class includes all such fixed choices. Merely proving hardness at one selected high level does not cross the frontier.^[2]^[3]
Inherent lower-bound property. No algorithm deciding the same problem has an elementary worst-case bound. A proof may use reductions or another lower-bound method, but a particular reduction is evidence for the property rather than a fifth defining role.^[1]^[2]

What It Is Not¶

“Nonelementary” does not mean mathematically elementary, nor does it mean that each input is slow in practice. Easy instances can exist. A poorly implemented decision procedure can have nonelementary runtime even where the underlying problem has a better algorithm; that observation alone cannot classify the problem. A fixed k-fold exponential bound, however daunting, still lies on the elementary side. An undecidable problem has no total decision algorithm and is excluded by the present decidable-problem scope.^[2]^[3]

Nor must every example be complete for one fast-growing complexity class. Schmitz introduces classes that distinguish tower-scale from still faster decidable problems; those classes refine the description of some instances. They do not replace the core all-fixed-heights boundary. Similarly, this entry names a property of a problem, not a particular complexity class understood as a set of problems.^[3]

Scope of Application¶

Meyer's MIT report addresses the truth problem for weak monadic second-order sentences over the successor structure, with second-order variables ranging over finite sets. Its institutional abstract states both decidability and non-elementary-recursiveness. This is a logical-theory decision question; the report's scanned proof details are not needed to assert its abstract-level result here.^[1]

Stockmeyer's thesis treats equivalence of star-free expressions: given two expressions built using operations including union, concatenation, and complement, decide whether they denote the same language. The original thesis separates this result from its study of expressions with an explicit squaring operation. The latter is a different syntax and lower-bound claim; neither should be substituted for the former. Schmitz's later §3.1 supplies a formal star-free grammar and a tower-completeness analysis.^[2]^[3]

These settings share the worst-case boundary but not the objects being compared. One asks whether a logical sentence is true; the other asks whether two language expressions denote the same set of words. The named problem, encoding, and theorem must stay attached to their own setting.^[1]^[2]

Clarity¶

To classify a candidate, first write down its yes/no question and an effective finite encoding. Establish that a decision procedure terminates. Then say which resource and computation model the lower-bound statement concerns. The decisive test is whether all fixed elementary-tower upper bounds are ruled out for algorithms solving that same question. Lower bounds at isolated fixed heights cannot establish it; an elementary upper bound for one correct algorithm refutes it.^[2]^[3]

A nonelementary lower bound is asymptotic. It does not say a particular short WS1S formula or a small pair of expressions consumes tower-scale resources. It says that as inputs grow, no elementary bound covers the worst case. Stockmeyer's original discussion explicitly frames a lower bound in terms of resources required on infinitely many inputs; that is compatible with many easy inputs.^[2]

Manages Complexity¶

The term marks a qualitative jump that labels such as “very exponential” can hide. An exponential, double exponential, or any fixed number of iterated exponentials can be absorbed by an elementary bound. A tower whose required height grows with input size cannot be absorbed by choosing one fixed height in advance. This comparison prevents a high finite level from being mistaken for the frontier itself.^[2]^[3]

The classification also separates decidability from feasible or elementary decision. The original WS1S result makes that distinction sharp: a guaranteed answer in principle coexists with a lower bound beyond all fixed towers. Schmitz's finer hierarchy is useful after this first boundary is established, because different nonelementary problems need not have the same growth rate.^[1]^[3]

Abstract Reasoning¶

Suppose a proposed algorithm solves the specified decision problem in time bounded by a tower of height seven in a polynomial of input size. Seven is fixed, so that algorithm supplies an elementary upper bound; the problem fails this entry's test even if the bound is unusable in practice. In contrast, a theorem showing that every decision procedure escapes each fixed height as inputs grow supports a nonelementary classification, provided that the problem is decidable. The number seven is an illustrative fixed height, not a claim about either source example.^[2]^[3]

The same reasoning is applied to the problem rather than to one chosen procedure. If a later elementary algorithm is found for the same formulation and encoding, a prior claim based only on an inefficient algorithm is overturned. If the language, syntax, or decision question changes, the proof must be re-evaluated; a result for star-free equivalence does not automatically apply to ordinary regular-expression equivalence or to Stockmeyer's distinct squaring syntax.^[2]^[3]

Knowledge Transfer¶

The WS1S and star-free cases transfer the test, not the proof. Each has a finite encoded input, a decidable yes/no question, a worst-case resource function, and a result beyond every fixed elementary tower. Logic formulas and formal-language expressions supply unlike carriers. The details that make one reduction work need not occur in the other setting.^[1]^[2]^[3]

For a new decision problem in verification or another field, one would need a fresh decidability argument, input/model specification, and suitable lower bound. Schmitz lists non-elementary problems across fields, but similarity of application area or the presence of nested syntax is not itself a proof. The category is reusable; each membership claim has its own evidence burden.^[3]

Examples¶

WS1S truth. Input: a sentence of weak monadic second-order logic of one successor over the standard natural-number successor structure. Question: is it true? The original report's abstract says that truth is decidable and not elementary-recursive. Role map: the sentence and interpretation specify the decision problem; formula length supplies input size; elementary-recursive resources supply the comparison frontier; Meyer's theorem supplies the beyond-frontier result. Schmitz discusses WS1S satisfiability in a later tower-scale analysis, but the present example retains Meyer's truth wording.^[1]^[3]

Star-free-expression equivalence. Input: two expressions for languages over an alphabet, allowing union, concatenation, and complement. Question: do they denote the same language? Stockmeyer's thesis states the equivalence problem is not elementary-recursive, and Schmitz uses it as a tower-scale example. Role map: the pair of expressions and the equality question fix the decidable problem; their encoded length fixes the size measure; fixed-height towers are the rejected upper-bound family; the original lower bound supplies the nonelementary differentia. This is a property of the equivalence question, not a claim that evaluating a particular tiny expression is hard.^[2]^[3]

Structural Tensions¶

No intrinsic two-sided design tension is required to define this complexity category. Restricted syntax may sometimes improve complexity while expressive syntax may increase it, but that tradeoff depends on a specific formalism and theorem. Stockmeyer's contrast between star-free expressions with complement and a separate squaring-expression problem illustrates why such a choice must be stated precisely; it does not license a universal claim that adding any operation always raises complexity.^[2]

Structural–Framed Character¶

The entry is structural within theoretical computer science: it states a quantifier-bearing relation between a decidable input family and asymptotic resource bounds. Vocabulary travel: “tower,” “elementary,” and “nonelementary” have ordinary-language uses, but here their complexity meanings require an encoded input and a computation model. The phrase does not travel unchanged to a merely difficult practical task. Evaluative weight: the formal classification is descriptive; calling a task infeasible in practice is a separate judgment about available resources and input sizes.^[2]^[3]

Institutional origin: published logic and complexity results, including the original Meyer and Stockmeyer theorems, establish this technical category. Their authority lies in the formal argument and problem definition rather than an institution's grant of status. Human-practice dependence: researchers choose the question, encoding, and resource convention, but after those are fixed the all-fixed-tower claim can be tested without a further social decision. Import versus recognition: applying the category to a new decision problem recognizes a proved asymptotic property; it does not confer nonelementarity by adopting a label. The source case must supply the theorem. Its character: a formal resource-bound classification with computational framing, whose fixed-height frontier remains invariant across the unlike logic and language examples once each problem is specified.^[1]^[2]^[3]

Structural Core vs. Domain Accent¶

The core is decidability, worst-case resource scaling by encoded input size, and failure of every fixed elementary upper bound for the same problem. Remove decidability and this scoped category no longer applies; remove the all-fixed-heights quantifier and it can collapse to a finite high-level hardness statement. WS1S formulas, star-free expression syntax, a particular lower-bound proof, and Schmitz's optional fast-growing class placement are case-specific accents.^[1]^[2]^[3]

The most portable skeleton here is resource growth with input size, and that belongs to the live Complexity (Time/Space) Prime. The computational residual that defines this entry—decidable yes/no problems compared with the elementary-recursive frontier—is domain-specific. The two source cases do not establish a new Prime beyond the existing resource-scaling abstraction. Could an all-fixed-bound frontier characterize unlike noncomputational systems under a comparably rigorous size and resource measure? That is a future-Prime question, requiring independently verified cases and a separate identity review. No such broader edge is asserted.^[3]

This entry presupposes Complexity (Time/Space).

Complexity (Time/Space) — strict composition/presupposes parent. The beyond-elementary claim requires the input-size resource-scaling relation, but the Prime is independently applicable to elementary problems and algorithms.
Computability — related. Decidability is required within this entry's stated scope, yet computability alone does not locate the elementary frontier. No second direct DAG edge is asserted.
Complexity Class — related domain-specific entry. A complexity class collects problems by resource limits. This entry classifies a decision problem by its beyond-elementary property; it is not itself one class or a member-to-class subsumption edge.

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¶

Do not confuse a fixed tower of huge height with a tower whose necessary height grows with input size; do not confuse one inefficient algorithm with an inherent problem lower bound; and do not confuse the undecidable with the decidable but nonelementary. Stockmeyer's star-free equivalence result uses complement and must not be replaced with the distinct squaring-expression result. Meyer's original WS1S truth statement must not be quoted as though it were Schmitz's satisfiability statement.^[1]^[2]^[3]

References¶

[1] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l

[2] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u

[3] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u