NONELEMENTARY
Encyclopedia
In computational complexity theory
, the complexity class
NONELEMENTARY is the complement of the class ELEMENTARY.
Example decidable problems in NONELEMENTARY this class are:
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
NONELEMENTARY is the complement of the class ELEMENTARY.
Example decidable problems in NONELEMENTARY this class are:
- the problem of regular expression equivalence with not
- decision problem for monadic second-order logicSecond-order logicIn logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory....
over trees - decision problem for term algebraTerm algebraIn 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 exactly the free magma generated by X...
s