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:

1. Função Zero. Retorna zero: f(x) = 0.
2. 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.
3. Funções de projeção: estas são usadas para ignorar argumentos. Por exemplo, f(a, b) = a é uma função de projeção.
4. 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.

1. Composição: applicar valores de uma função elementar recursiva qualquer como argumento para outra função elementar recursiva. Em f(x₁, ..., x_n) = h(g₁(x₁, ..., x_n), ..., g_m(x₁, ..., x_n)) é recursiva elementar se h é recursiva elementar e cada g_i é também recursiva elementar.
2. 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.
3. 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.

Ver também

• Elementary function arithmetic
• Função recursiva primitiva
• Grzegorczyk hierarchy
• EXPTIME

Referências

• Rose, H.E., Subrecursion: Functions and hierarchies, Oxford University Press, 1984. ISBN 0-19-853189-3