# ELEMENTAR (complexidade)

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

## Definição

As definições de funções recursivas elementares são as mesmas que as de funções recursivas primitivas, exceto que a recursão primitiva é substituída por somatório e produtório limitados. Todas as funções trabalham sobre números naturais. As funções básicas, todas elas recursivas elementares, são:
* Função Zero. Retorna zero: f(x) = 0.
* Função Sucessor: f(x) = x + 1. Isto é comumente denotado por S, como em S(x). Repetindo-se a função sucessor pode-se atingir a função de adição.
* Funções de projeção: estas são usadas para ignorar argumentos. Por exemplo, f(a, b) = a é uma função de projeção.
* Função Subtração: f(x, y) = x − y se y < x, ou 0 se y ≥ x. Esta função é usada para definir condicionais e para definir iteração.
Destas funções básicas, podemos construir outras funções recursivas elementares.
* Composição: applicar valores de uma função elementar recursiva qualquer como argumento para outra função elementar recursiva. Em f(x$_1$, ..., x$_n$) = h(g$_1$(x$_1$, ..., x$_n$), ..., g$_m$(x$_1$, ..., x$_n$)) é recursiva elementar se h é recursiva elementar e cada g$_i$ é também recursiva elementar.
* Somatório limitado: $f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})$ é recursiva elementar se g é recursiva elementar.
* Produtório limitado: $f(m,x_{1},\ldots ,x_{n})=\prod \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})$ é recursiva elementar se g é recursiva elementar.

## Funções elementares recursivas inferiores

Funções elementares recursivas inferiores seguem as definições acima, exceto para o Produtório, que não é permitido. Isto é, uma função elementar recursiva inferior deve ser uma função Zero, Sucessor ou de Projeção, pode ser também uma composição de outras funções elementares recursivas inferiores ou ainda o Somatório limitado de outra função elementar recursiva inferior.
Enquanto funções elementares recursivas têm crescimento potencialmente mais que exponencial, funções elementares recursivas inferiores têm crescimento polinomial.

## Base para ELEMENTAR

A classe de funções elementares coincide com o fecho com respeito à composição das projeções e um dos seguintes conjuntos de funções: $\{n+1,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,n^{m}\}$, $\{n+m,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,2^{n}\}$, $\{n+m,n^{2},n\,{\bmod {\,}}m,2^{n}\}$, onde $n\,{\stackrel {.}{-}}\,m=\max\{n-m,0\}$ é a função Subtração definida acima.

## Caracterização Descritiva

Em complexidade descritiva, ELEMENTAR é equivalente à classe de consultas de ALTA ORDEM (HO - HIGH ORDER). Isto significa que toda linguagem na classe de complexidade ELEMENTAR pode ser escrita como uma fórmula de alta ordem que somente é verdadeira para os elementos nesta linguagem. Mais precisamente, $\mathrm {NTIME} (2^{2^{\cdots {2^{O(n)}}}})=\exists\mathrm {HO} ^{i}$, onde $\cdots$ indica uma torre de i exponenciações e $\exists\mathrm {HO} ^{i}$ é a classe de consultas que começam com quantificadores existenciais de iésima ordem e então uma fórmula de (i − 1)ésima ordem.