Article · Português
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.
Abstract from DBpedia / Wikipedia · CC BY-SA