ELEMENTAR (complexidade)

Esta página ou se(c)ção precisa ser formatada para o padrão wiki. Por favor ajude a formatar esta página de acordo com as diretrizes estabelecidas. (Dezembro de 2024)

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

${\displaystyle {\begin{aligned}\mathrm {ELEMENTARY} &=\mathrm {EXP} \cup \mathrm {2EXP} \cup \mathrm {3EXP} \cup \cdots \\&=\mathrm {DTIME} (2^{n})\cup \mathrm {DTIME} (2^{2^{n}})\cup \mathrm {DTIME} (2^{2^{2^{n}}})\cup \cdots \end{aligned}}}$

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, ${\displaystyle O(2^{2^{n}})}$), PR permite hiper operadores mais gerais (por exemplo, tetração) que não estão contidos em ELEMENTAR.