In
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 by ...
, a nonelementary problem is a problem that is not a member of the class
ELEMENTARY. 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 whethe ...
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 t ...
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
* deciding β-convertibility of two closed terms in
typed lambda calculus
* 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 additi ...
s; it is
Ackermann-complete.
References
Complexity classes
{{Comp-sci-theory-stub