ELEMENTARY (complexité)

La définition des fonctions récursives élémentaires est la même que celle des fonctions primitives récursives, sauf que le schéma de construction récursive primitive est remplacé par la somme et le produit borné. Toutes les fonctions agissent sur les entiers naturels. Les fonctions de bases sont :

1. La fonction nulle. Constamment nulle : ${\displaystyle f(x)=0}$  ;
2. La fonction successeur : ${\displaystyle f(x)=x+1}$ , qui est souvent notée S. En itérant cette fonction, on obtient l'addition ;
3. Les projections : ces fonctions servent à ignorer des arguments. Par exemple, ${\displaystyle f(a,b)=a}$ est une projection ;
4. La soustraction : ${\displaystyle f(x,y)=x-y}$ si ${\displaystyle y<x}$ , ou 0 si ${\displaystyle y\geqslant x}$ . Cette fonction est utilisée pour créer des conditions et faire des itérations.

À partir de ces fonctions de base, on peut créer d'autres fonctions.

1. La composition de fonctions élémentaires. ${\displaystyle f(x_{1},\ldots ,x_{n})=h(g_{1}(x_{1},\ldots ,x_{n}),\ldots ,g_{m}(x_{1},\ldots ,x_{n}))}$ est élémentaire si ${\displaystyle h}$ et tous les ${\displaystyle g_{i}}$ sont élémentaires.
2. Somme bornée : ${\displaystyle f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}$ est élémentaire si ${\displaystyle g}$ est élémentaire.
3. Produit borné : ${\displaystyle f(m,x_{1},\ldots ,x_{n})=\prod \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}$ est élémentaire si ${\displaystyle g}$ est élémentaire.

Les fonctions récursives élémentaires inférieures suivent la définition précédente à ceci près que l'on exclut le produit borné. Par conséquent, une fonction est élémentaire inférieure si c'est une projection, le successeur, la fonction nulle ou une composée ou une somme bornée d'une autre fonction élémentaire inférieure.

Alors que les fonctions élémentaires peuvent avoir une croissance exponentielle et contiennent la hiérarchie exponentielle, les fonctions élémentaires inférieures n'ont que des croissances polynomiales.

La classe des fonctions élémentaires coïncide avec la clôture par la composition des projections et d'un des ensembles de fonction suivant : ${\displaystyle \{n+1,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,n^{m}\}}$ , ${\displaystyle \{n+m,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,2^{n}\}}$ , ${\displaystyle \{n+m,n^{2},n\,{\bmod {\,}}m,2^{n}\}}$ , où ${\displaystyle n\,{\stackrel {.}{-}}\,m=\max\{n-m,0\}}$ est la soustraction dans ${\displaystyle \mathbb {N} }$ définie plus haut^[1].

Les fonctions ${\displaystyle (x,y)\mapsto xy}$ , ${\displaystyle (x,y)\mapsto x^{y}}$ et ${\displaystyle x\mapsto x!}$ sont élémentaires. La première peut être facilement construite par somme bornée, la seconde, par produit bornée. La dernière demande un peu plus de travail et utilise la soustraction naturelle.

Certains problèmes récursifs naturels sont en dehors de ELEMENTARY et sont donc dans la classe NONELEMENTARY. En particulier, il existe des problèmes primitifs récursifs qui ne sont pas dans ELEMENTARY. On sait que

LOWER-ELEMENTARY ${\displaystyle \subsetneq }$ EXPTIME ${\displaystyle \subsetneq }$ ELEMENTARY ${\displaystyle \subsetneq }$ PR ${\displaystyle \subsetneq }$ R

Alors que ELEMENTARY ne contient que des itérations bornées de l'exponentiation (par exemple, ${\displaystyle O(2^{2^{n}})}$ ), PR autorise des hyperopérations plus générales (par exemple, la tétration) qui ne sont pas dans ELEMENTARY

Pour toute fonction ${\displaystyle f:\mathbb {N} ^{k+1}\rightarrow \mathbb {N} ^{r}}$ , on peut définir sa minimisation bornée, notée ${\displaystyle \mathrm {MinB} (f)}$ , comme la fonction

${\displaystyle {\begin{aligned}\mathrm {MinB} (f):\mathbb {N} ^{k+1}&\rightarrow \mathbb {N} \\(n,m)&\mapsto {\begin{cases}\min\{i\leqslant n\mid f(i,m)=d_{r}(0)\}&{\text{s'il existe un tel }}i\\n+1&{\text{sinon}}\end{cases}}\end{aligned}}}$

où ${\displaystyle d_{r}(x)}$ dénote le ${\displaystyle r}$ -uplet ${\displaystyle (x,\ldots ,x)}$ .

ELEMENTARY est stable par minimisation bornée.

Démonstration

Soit ${\displaystyle f\in ELEMENTARY(\mathbb {N} ^{n}\times \mathbb {N} ,\mathbb {N} ^{m})}$ . On pose (avec ${\displaystyle {\dot {-}}}$ qui représente la soustraction naturelle)

${\displaystyle h(u,y)=\sum \limits _{i=0}^{y}(1{\dot {-}}f(u,i)))}$

où ${\displaystyle u\in \mathbb {N} ^{n}}$ et ${\displaystyle y\in \mathbb {N} }$ et

${\displaystyle g(u,x)=h(u,y)(1{\dot {-}}(h(u,x){\dot {-}}x))}$

On a alors ${\displaystyle \mathrm {MinB} (y\mapsto f(u,y))(x)=g(u,x)}$ or ${\displaystyle g}$ est clairement élémentaire puisque obtenue par produit, différence et somme bornée. Donc la minimisation bornée d'une fonction élémentaire est élémentaire.

Soit ${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} ^{r}}$ , ${\displaystyle g:\mathbb {N} ^{k+r+1}\rightarrow \mathbb {N} ^{r}}$ et ${\displaystyle j:\mathbb {N} ^{k+1}\rightarrow \mathbb {N} ^{r}}$ .On définit par la récursion bornée ${\displaystyle h=\mathrm {RecB} (f,g,j)}$ par la fonction définit par

${\displaystyle {\begin{aligned}h(0,m)&=f(m)\\h(n+1,m)&=g(n,h(n,m)m)\end{aligned}}}$

et qui doit vérifier${\displaystyle h(n,m)\leqslant j(n,m)}$ . ${\displaystyle j}$ ne sert pas à construire la fonction mais sert de certificat concernant sa croissance.

ELEMENTARY est stable par récursion bornée.

Définition

Un prédicat est dit élémentaire si sa fonction indicatrice est une fonction élémentaire.

Propriétés

Soit ${\displaystyle P}$ un prédicat sur ${\displaystyle \mathbb {N} ^{k+1}}$ . On appelle les quantification bornées de ce prédicat, les prédicats sur ${\displaystyle \mathbb {N} ^{k}}$

${\displaystyle {\begin{aligned}\forall i\leqslant n,&P(i,m)\\\exists i\leqslant n:&P(i,m)\end{aligned}}}$

pour tout entier naturel ${\displaystyle n}$ .

La classe des prédicats élémentaire est stable par quantification bornée.

La classe des prédicats élémentaire est stable pour les opérations logiques ${\displaystyle \neg }$ , ${\displaystyle \wedge }$ et ${\displaystyle \vee }$ .

En complexité descriptive, ELEMENTARY est égale à la classe HO^[2]. Cela signifie que tout langage de ELEMENTARY peut être décrit comme une formule de HO qui est vraie seulement pour les éléments de HO. Plus précisément, ${\displaystyle \mathrm {NTIME} (2^{2^{{\text{⋰ }}^{2^{O(n)}}}})=\exists {}HO^{i}}$ , où ${\displaystyle {\text{⋰ }}}$ indique une suite de ${\displaystyle i}$ exponentiations et ${\displaystyle \exists {}HO^{i}}$ est une classe de formules qui commencent avec des quantificateurs existentiels du ${\displaystyle i}$ ème ordre et donc une formule du (i − 1)ème ordre.

• (en) La classe ELEMENTARY sur le Complexity Zoo