NONELEMENTARY

In computational complexity theory, the complexity class 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 logic over trees
• decision problem for term algebras

P ≟ NP

This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Complexity classes Theoretical computer science stubs Wikimedia Foundation. 2010. Игры ⚽ Нужно сделать НИР? Altstadt (Frankfurt am Main) History of Gyeongju Look at other dictionaries: nonelementary — [spelling only] …   English World dictionary Nonelementary integral — In mathematics, a nonelementary antiderivative is an antiderivative for which it can be shown that there exists no formula in terms of elementary functions (i.e. involving polynomials, and the standard functions sin, cos, exp, and so on). A… …   Wikipedia nonelementary — adj. * * * …   Universalium nonelementary — adjective Not elementary …   Wiktionary nonelementary — adj …   Useful english dictionary Nonlinear system — Not to be confused with Non linear editing system. This article describes the use of the term nonlinearity in mathematics. For other meanings, see nonlinearity (disambiguation). In mathematics, a nonlinear system is one that does not satisfy the… …   Wikipedia metalogic — /met euh loj ik/, n. the logical analysis of the fundamental concepts of logic. [1835 45; META + LOGIC] * * * Study of the syntax and the semantics of formal languages and formal systems. It is related to, but does not include, the formal… …   Universalium Integral — This article is about the concept of integrals in calculus. For the set of numbers, see integer. For other uses, see Integral (disambiguation). A definite integral of a function can be represented as the signed area of the region bounded by its… …   Wikipedia Basel problem — The Basel problem is a famous problem in number theory, first posed by Pietro Mengoli in 1644, and solved by Leonhard Euler in 1735. Since the problem had withstood the attacks of the leading mathematicians of the day, Euler s solution brought… …   Wikipedia ELEMENTARY — In computational complexity theory, the complexity class ELEMENTARY is the union of the classes in the exponential hierarchy.: egin{matrix} m{ELEMENTARY} = m{EXP}cup m{2EXP}cup m{3EXP}cupcdots = m{DTIME}(2^{n})cup m{DTIME}(2^{2^{n)cup… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”