computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

, a nonelementary problem is a problem that is not a member of the class

ELEMENTARY Elementary may refer to: Arts, entertainment, and media Music * ''Elementary'' (Cindy Morgan album), 2001 * ''Elementary'' (The End album), 2007 * ''Elementary'', a Melvin "Wah-Wah Watson" Ragin album, 1977 Other uses in arts, entertainment, a ...

. As a class it is sometimes denoted as NONELEMENTARY. Examples of nonelementary problems that are nevertheless decidable include: * the problem of regular expression equivalence with complementation * the

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...

for

monadic second-order logic In mathematical logic, monadic second-order logic (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets. It is particularly important in the logic of graphs, because of Courcelle's ...

over

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

s (see S2S) * the decision problem for

term algebra In universal algebra and mathematical logic, a term algebra is a freely generated algebraic structure over a given signature. For example, in a signature consisting of a single binary operation, the term algebra over a set ''X'' of variables is exa ...

s * satisfiability of

W. V. O. Quine W. may refer to: * SoHo (Australian TV channel) (previously W.), an Australian pay television channel * ''W.'' (film), a 2008 American biographical drama film based on the life of George W. Bush * "W.", the fifth track from Codeine's 1992 EP ''Bar ...

's fluted fragment of

first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...

* deciding β-convertibility of two closed terms in

typed lambda calculus A typed lambda calculus is a typed formalism that uses the lambda-symbol (\lambda) to denote anonymous function abstraction. In this context, types are usually objects of a syntactic nature that are assigned to lambda terms; the exact nature of a ...

* reachability in

vector addition system A vector addition system (VAS) is one of several mathematical modeling languages for the description of distributed systems. Vector addition systems were introduced by Richard M. Karp and Raymond E. Miller in 1969, and generalized to vector addit ...

s; it is Ackermann-complete.

References

Complexity classes {{Comp-sci-theory-stub