ELEMENTARY (complexité)

En théorie de la complexité, la classe de complexité ELEMENTARY des fonctions récursives élémentaires est la réunion des classes de la hiérarchie exponentielle.

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

Le nom a été introduit par László Kalmár, dans le contexte des fonctions calculables et de l'indécidabilité où la plupart des problèmes ne sont pas élémentaires. Un problème de décision est dit non élementaire s'il n'est pas dans ELEMENTARY.

Définition

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 :

La fonction nulle. Constamment nulle : $f(x)=0$ ;
La fonction successeur : $f(x)=x+1$ , qui est souvent notée S. En itérant cette fonction, on obtient l'addition ;
Les projections : ces fonctions servent à ignorer des arguments. Par exemple, $f(a,b)=a$ est une projection ;
La soustraction : $f(x,y)=x-y$ si $y<x$ , ou 0 si $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.

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

Fonctions récursives élémentaires inférieures

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.

Fonctions de base de ELEMENTARY

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 : $\{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}\}$ , où $n\,{\stackrel {.}{-}}\,m=\max\{n-m,0\}$ est la soustraction dans $\mathbb {N}$ définie plus haut^[1].

Exemples

Les fonctions $(x,y)\mapsto xy$ , $(x,y)\mapsto x^{y}$ et $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.

Relations entre classes

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

\subsetneq

EXPTIME

\subsetneq

ELEMENTARY

\subsetneq

PR

\subsetneq

R

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

Propriétés

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

{\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ù $d_{r}(x)$ dénote le $r$ -uplet $(x,\ldots ,x)$ .

ELEMENTARY est stable par minimisation bornée.

Démonstration

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

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

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

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

On a alors $\mathrm {MinB} (y\mapsto f(u,y))(x)=g(u,x)$ or $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 $f:\mathbb {N} ^{k}\rightarrow \mathbb {N} ^{r}$ , $g:\mathbb {N} ^{k+r+1}\rightarrow \mathbb {N} ^{r}$ et $j:\mathbb {N} ^{k+1}\rightarrow \mathbb {N} ^{r}$ . On définit par la récursion bornée $h=\mathrm {RecB} (f,g,j)$ par la fonction définit par

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

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

ELEMENTARY est stable par récursion bornée.

Prédicats élémentaires

Définition

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

Propriétés

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

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

pour tout entier naturel $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 $\neg$ , $\wedge$ et $\vee$ .

Caractérisation descriptive

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, $\mathrm {NTIME} (2^{2^{{\text{⋰ }}^{2^{O(n)}}}})=\exists {}HO^{i}$ , où ${\text{⋰ }}$ indique une suite de $i$ exponentiations et $\exists {}HO^{i}$ est une classe de formules qui commencent avec des quantificateurs existentiels du $i$ ème ordre et donc une formule du (i − 1)ème ordre.

Liens externes

(en) La classe ELEMENTARY sur le Complexity Zoo

Références

↑ Mazzanti, S., "Plain Bases for Classes of Primitive Recursive Functions", Mathematical Logic Quarterly, 48 (2002) 93–104
↑ Lauri Hella and José María Turull-Torres, Computing queries with higher-order logics, vol. 355, Essex, UK, Elsevier Science Publishers Ltd., 2006, 197–214 p. (ISSN 0304-3975, DOI 10.1016/j.tcs.2006.01.009, lire en ligne)

Rose, H.E., "Subrecursion: Functions and hierarchies", Oxford University Press, New York, USA, 1984. (ISBN 0-19-853189-3)

Voir aussi

Portail de l'informatique théorique

[1] Mazzanti, S., "Plain Bases for Classes of Primitive Recursive Functions", Mathematical Logic Quarterly, 48 (2002) 93–104

[2] Lauri Hella and José María Turull-Torres, Computing queries with higher-order logics, vol. 355, Essex, UK, Elsevier Science Publishers Ltd., 2006, 197–214 p. (ISSN 0304-3975, DOI 10.1016/j.tcs.2006.01.009, lire en ligne)

[1]

[2]