About: ELEMENTARY     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:Group100031264, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FELEMENTARY

In computational complexity theory, the complexity class ELEMENTARY of elementary recursive functions is the union of the classes The name was coined by László Kalmár, in the context of recursive functions and undecidability; most problems in it are far from elementary. Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY. Most notably, there are primitive recursive problems that are not in ELEMENTARY. We know LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R

AttributesValues
rdf:type
rdfs:label
  • ELEMENTARY (ca)
  • ELEMENTARY (es)
  • ELEMENTARY (en)
  • ELEMENTARY (complexité) (fr)
  • ELEMENTARY (ja)
  • ELEMENTAR (complexidade) (pt)
  • ELEMENTARY (zh)
rdfs:comment
  • En teoria de la complexitat, la classe de complexitat ELEMENTARY de les funcions recursives primitives és la unió de les classes El nom va ser proposat per László Kalmár, en el context de funcions recursives i indecibilitat. Alguns problemes recursius cauen fora de la classe ELEMENTARY i per tant son dins de NO-ELEMENTARY. Particularment, hi ha problemes a les classes associades a la recursió primitiva que no està a ELEMENTARY. Se sap que LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R (ca)
  • En théorie de la complexité, la classe de complexité ELEMENTARY des fonctions récursives élémentaires est la réunion des classes de la . Le nom a été introduit par László Kalmár, dans le contexte des fonctions calculables et de l'indécidabilité où la plupart des problèmes ne sont pas élémentaires. Un problème de décision est dit non élementaire s'il n'est pas dans ELEMENTARY. (fr)
  • 計算複雑性理論において ELEMENTARY とはの和集合で表される複雑性クラスである。 クラス ELEMENTARY に属す関数は初等帰納的（しょとうきのうてき、英: elementary recursive）あるいは単に初等的と呼ばれる。この名称はによる造語である。 帰納的関数や決定不能性の文脈で扱われる多くの問題は ELEMENTARY よりも高いレベルにある。いくつかの帰納的問題は ELEMENTARY を超える。すなわち NONELEMENTARY となる。とくに注目されるのは、原始帰納的問題で ELEMENTARY に属さないものが存在することである。次が知られている。 LOWER-ELEMENTARY EXPTIME ELEMENTARY PR R ELEMENTARY は指数関数の定数回の入れ子（例えば ）を含むが、PRは指数関数の一般化であるハイパー演算子で ELEMENTARY に属さないもの（例えばテトレーション）を含む。 (ja)
  • 在計算複雜度理論裡面，複雜度類ELEMENTARY是所有指數譜系裡面的複雜度類聯集： 這名稱最早是為了探討可計算函數和不可判定問題，由所提出；most problems in it are far from elementary。Some natural recursive problems lie outside ELEMENTARY, and are thus 。相當值得注意的，有一些原始遞歸函數問題不在ELEMENTARY內。我們已知： LOWER-ELEMENTARY EXPTIME ELEMENTARY 與ELEMENTARY僅包含有限的冪（例如，）比較，PR使用的 超運算更一般化（例如，tetration），因此PR不包含於ELEMENTARY。 (zh)
  • En teoría de la complejidad computacional, la clase de complejidad ELEMENTARY de las funciones recursivas elementales es la unión de las clases El nombre fue acuñado por László Kalmár, en el contexto de funciones recursivas e indecidibilidad; a pesar de su nombre, la mayoría de problemas en esta clase distan mucho de ser elementales. Algunos problemas naturalmente recursivos quedan fuera de ELEMENTARY, por lo que pertenecen más bien a . Más particularmente, hay problemas en las clases asociadas a la recursión primitiva y a la que no están en ELEMENTARY.​ Sabemos que (es)
  • In computational complexity theory, the complexity class ELEMENTARY of elementary recursive functions is the union of the classes The name was coined by László Kalmár, in the context of recursive functions and undecidability; most problems in it are far from elementary. Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY. Most notably, there are primitive recursive problems that are not in ELEMENTARY. We know LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R (en)
  • O conteúdo desta página é tradução do artigo em inglês en:ELEMENTARY; Na teoria da complexidade computational, a classe de complexidade ELEMENTAR das funções recursivas elementares é a união das classes O nome foi criado por László Kalmár, no contexto de funções recursivas e de indecidibilidade; a maioria dos problemas nesta classe está longe de ser elementar. Alguns problemas naturais de recursão estão fora de ELEMENTAR, sendo assim NÃO-ELEMENTARES. Notavelmente, existem problemas recursivos primitivos que não pertencem a ELEMENTAR. Sabemos que LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R (pt)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • En teoria de la complexitat, la classe de complexitat ELEMENTARY de les funcions recursives primitives és la unió de les classes El nom va ser proposat per László Kalmár, en el context de funcions recursives i indecibilitat. Alguns problemes recursius cauen fora de la classe ELEMENTARY i per tant son dins de NO-ELEMENTARY. Particularment, hi ha problemes a les classes associades a la recursió primitiva que no està a ELEMENTARY. Se sap que LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R (ca)
  • In computational complexity theory, the complexity class ELEMENTARY of elementary recursive functions is the union of the classes The name was coined by László Kalmár, in the context of recursive functions and undecidability; most problems in it are far from elementary. Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY. Most notably, there are primitive recursive problems that are not in ELEMENTARY. We know LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R Whereas ELEMENTARY contains bounded applications of exponentiation (for example, ), PR allows more general hyper operators (for example, tetration) which are not contained in ELEMENTARY. (en)
  • En théorie de la complexité, la classe de complexité ELEMENTARY des fonctions récursives élémentaires est la réunion des classes de la . Le nom a été introduit par László Kalmár, dans le contexte des fonctions calculables et de l'indécidabilité où la plupart des problèmes ne sont pas élémentaires. Un problème de décision est dit non élementaire s'il n'est pas dans ELEMENTARY. (fr)
  • En teoría de la complejidad computacional, la clase de complejidad ELEMENTARY de las funciones recursivas elementales es la unión de las clases El nombre fue acuñado por László Kalmár, en el contexto de funciones recursivas e indecidibilidad; a pesar de su nombre, la mayoría de problemas en esta clase distan mucho de ser elementales. Algunos problemas naturalmente recursivos quedan fuera de ELEMENTARY, por lo que pertenecen más bien a . Más particularmente, hay problemas en las clases asociadas a la recursión primitiva y a la que no están en ELEMENTARY.​ Sabemos que LOWER-ELEMENTARY EXPTIME ELEMENTARY PR R Mientras que ELEMENTARY contiene aplicaciones acotadas de exponenciación (por ejemplo, ), PR permite hiperoperadores (por ejemplo, tetración) los cuales no están contenidos en ELEMENTARY. (es)
  • 計算複雑性理論において ELEMENTARY とはの和集合で表される複雑性クラスである。 クラス ELEMENTARY に属す関数は初等帰納的（しょとうきのうてき、英: elementary recursive）あるいは単に初等的と呼ばれる。この名称はによる造語である。 帰納的関数や決定不能性の文脈で扱われる多くの問題は ELEMENTARY よりも高いレベルにある。いくつかの帰納的問題は ELEMENTARY を超える。すなわち NONELEMENTARY となる。とくに注目されるのは、原始帰納的問題で ELEMENTARY に属さないものが存在することである。次が知られている。 LOWER-ELEMENTARY EXPTIME ELEMENTARY PR R ELEMENTARY は指数関数の定数回の入れ子（例えば ）を含むが、PRは指数関数の一般化であるハイパー演算子で ELEMENTARY に属さないもの（例えばテトレーション）を含む。 (ja)
  • O conteúdo desta página é tradução do artigo em inglês en:ELEMENTARY; Na teoria da complexidade computational, a classe de complexidade ELEMENTAR das funções recursivas elementares é a união das classes O nome foi criado por László Kalmár, no contexto de funções recursivas e de indecidibilidade; a maioria dos problemas nesta classe está longe de ser elementar. Alguns problemas naturais de recursão estão fora de ELEMENTAR, sendo assim NÃO-ELEMENTARES. Notavelmente, existem problemas recursivos primitivos que não pertencem a ELEMENTAR. Sabemos que LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R Ao passo que ELEMENTAR possui aplicações limitadas de exponenciação (por exemplo, ), PR permite hiper operadores mais gerais (por exemplo, tetração) que não estão contidos em ELEMENTAR. (pt)
  • 在計算複雜度理論裡面，複雜度類ELEMENTARY是所有指數譜系裡面的複雜度類聯集： 這名稱最早是為了探討可計算函數和不可判定問題，由所提出；most problems in it are far from elementary。Some natural recursive problems lie outside ELEMENTARY, and are thus 。相當值得注意的，有一些原始遞歸函數問題不在ELEMENTARY內。我們已知： LOWER-ELEMENTARY EXPTIME ELEMENTARY 與ELEMENTARY僅包含有限的冪（例如，）比較，PR使用的 超運算更一般化（例如，tetration），因此PR不包含於ELEMENTARY。 (zh)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 67 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software