# Complexité générique des algorithmes

La complexité générique est un domaine particulier de la complexité algorithmique qui concerne l’étude de la complexité de problèmes algorithmiques pour « la plupart des données ».
La complexité générique est une façon de mesurer la complexité d'un problème algorithmique en négligeant un petit ensemble d'entrées non représentatives et en considérant la complexité dans le pire des cas sur les entrées restantes. La concept de « petit ensemble » est définie en termes de densité asymptotique. L'efficacité apparente des algorithmes mesurée par leur complexité générique provient du fait que, pour une grande variété de problèmes informatiques concrets, les cas les plus difficiles semblent être rares, alors que les cas typiques sont, eux, relativement faciles.
Cette approche de la complexité prend son origine dans la théorie combinatoire des groupes qui a une tradition dans l'étude de problèmes algorithmiques qui remonte au début du XXe siècle. La notion de complexité générique a été introduit en 2003 dans des articles de Kapovich, Miasnikov, Schupp et Shpilrain$^,$. Les auteurs montrent que, pour une large classe de groupes finiment engendrés, la complexité générique de quelques problèmes de décision classiques de la théorie combinatoire des groupes, à savoir le problème du mot, le problème de conjugaison (en), ou le problème d'appartenance, est en fait linéaire.
Une introduction et un survol de la complexité générique sont donnés dans un texte de R. Gilman, A. G. Miasnikov, A. D. Myasnikov, et A. Ushakov. Les livres de Miasnikov, Shpilrain et Ushakov$^,$ traitent principalement des résultats des auteurs relativement à la cryptographie.

## Définitions
### Densité asymptotique

Soit $I$ un ensemble infini de données pour un problème algorithmique.
Définition. Une fonction taille sur $I$ est une fonction$\sigma :I\to \mathbb {N}$ qui a une image infinie. La boule de rayon $n$ est $B_{n}=\{x\in I\mid \sigma (x)\leq n\}$.
Si les données sont codées comme mots sur un alphabet fini, la taille est fréquemment la longueur du mot.
Soit $\{\mu _{n}\}$ un ensemble de distributions de probabilité, où $\mu _{n}$$\mu _{n}$ est une distribution de probabilité sur la boule $B_{n}$. Si les boules $B_{n}$ sont finies, on peut prendre pour $\mu _{n}$ la distribution uniforme, et c'est le cas le plus fréquent.
Définition. La densité asymptotique d'une partie $X\subset I$ est
    $\rho (X)=\lim _{n\to \infty }\mu _{n}(X\cap B_{n})$,
quand cette limite existe.
Quand les boules $B_{n}$ sont finies et $\mu _{n}$ est la mesure uniforme, on a
    $\rho (X)=\lim {\frac {|X\cap B_{n}|}{|B_{n}|}}.$
Dans ce cas, il est souvent commode d'utiliser les sphères $I_{n}=\{x\in I\mid \sigma (x)=n\}$ à la place des boules, et de définir
    $\rho '(X)=\lim {\frac {|X\cap I_{n}|}{|I_{n}|}}$.
Par le théorème de Stolz-Cesàro, la densité $\rho (X)$ existe si $\rho '(X)$ existe, et dans ce cas les deux valeurs sont égales.
Definition. Une partie $X\subseteq I$ est générique si $\rho (X)=1$ et elle est négligeable si $\rho (X)=0$. $X$ est exponentiellement (respectivement superpolynomialement) générique si la vitesse de convergence vers la limite $\rho (X)$ est exponentielle (respectivement. superpolynomiale). Une partie $X\subseteq I$ est fortement générique s'il existe $\varepsilon >0$ telle que
    ${\frac {|I_{n}\setminus X|}{|I_{n}|}}\leq 2^{\varepsilon n}$
pour presque tout entier naturel $n$.

### Classes de complexité générique

Definition. Un algorithme est dans la classe GenP (pour « generically polynomial time ») s'il ne donne jamais de réponse fausse, et s'il donne une réponse juste en temps polynomial (en) sur un ensemble générique de données. Un problème est lui-même dans la classe GenP s'il possède un algorithme dans GenP. On définit de même GenL (« generically linear time ») comme classe pour le temps linéaire (en)), GenE (« generically exponential time », pour le temps exponentiel avec un exposant linéaire) , GenExp (« generically exponential time » ), etc. ExpGenP est la sous-classe de GenP pour lequel l'ensemble générique correspondant est exponentiellement générique.
Plus généralement, pour toute fonction $f:\mathbb {N} \to \mathbb {N}$, on peut définir la classe Gen(f) correspondant à la complexité en temps $O(f)$ sur un ensemble générique de données.
Definition. Un algorithme résout génériquement un problème s'il ne donne jamais de réponse fausse et s'il donne un réponse juste sur un ensemble générique de données. Un problème est génériquement résoluble s'il peut être résolu génériquement par un algorithme.

## Théorie et applications
### Problèmes en théorie combinatoire des groupes

* Les célèbres problèmes indécidables que sont le problème des mots, le problème de la conjugaison et le problème de l'apparenance, sont décidables en temps générique polynomial.
* Le problème des mots et le problème de la conjugaison sont dans la classe GenP pour les groupes finiment présentés.
* Le problème bien connu de l'énumération des cosets (en) possède une borne supérieure calculable sur un ensemble générique d'entrées.
* L'algorithme de Whitehead qui teste si un élément d'un groupe libre est envoyé sur un autre par un automorphisme a une borne supérieure exponentielle dans le pire cas, mais s'avère être efficace en pratique. En fait, il est dans la classe GenL.
* Le problème de conjugaison dans les extensions HNN peut être insoluble même pour les groupes libres. En revanche, il est en temps générique cubique. Pour certains groupes, des résultats plus précis ont été obtenus par Diekert et ses coauteurs

### Le problème de l’arrêt et le problème de correspondance de Post

* Le problème de l'arrêt des machines de Turing avec une bande infinie d'un côté one-sided tape est la plupart du temps facilement décidable easily decidable most of the time; il est dans la classe GenP.
* Le problème de correspondance de Post est dans ExpGenP.

### Arithmétique de Presburger

Le problème de décision pour l'arithmétique de Presburger admet un borne inférieure doublement exponentielle dans le pire des cas et une borne supérieure triplement exponentielle dans le pire des cas. On sait que la complexité générique n'est pas dans ExpGenP.

### Problèmes NP-complets

Il est bien connu que des problèmes NP-complets peuvent être en moyenne faciles, et il n'est pas surprenant que quelques-uns sont aussi génériquement faciles.
* Le problème 3-SAT est dans la classe ExpGenP.
* Le subset sum problem est dans la classe GenP.

### Fonctions à sens unique

Il existe une version pour la complexité générique de la notion de fonction à sens unique qui donne la même classe de fonctions mais permet d'autres hypothèses sur la sécurité.

### Cryptographie à clé publique

Tout un ensemble de travaux$^,$$^,$ est consacré à la cryptanalyse du protocole d'échange de clés de Anshel-Anshel-Goldfeld (en) dont la sécurité est basé sur des hypothèses sur le groupe de tresses. Cette série culmine dans un article qui applique des techniques de complexité générique pour obtenir une analyse complète de l'attaque basés sur la longueur et des conditions dans lesquelles elle aboutit. Le point de vue générique suggère également une attaque nouvelle appelée attaque par quotient, et une version plus sure du protocole de Anshel-Anshel-Goldfeld.

### Minimisation d'automates par l'algorithme de Brzozowski

L'algorithme de Brzozowski pour la minimisation des automates finis est un algorithme dont la complexité est exponentielle dans le pire des cas. Il est génériquement super-polynomial. Dans certains cas, on peut en analyser la complexité en moyenne.

### Une collection de résultats théorique généraux

Le théorème de Rice stipule que pour un ensemble $F$ de fonction partielles calculables de $\mathbb {N}$ dans $\{0,1\}$, il est indécidable si la fonction calculée par une machine de machine de Turing donnée est une fonction de $F$, sauf dans les cas triviaux où $F$ est vide ou son complémentaire est vide. La version générique de ce théorème est la suivante :
Théorème. Soit $I$ l'ensemble de toutes les machines de Turing. Pour un ensemble $F$ de fonctions de $\mathbb {N}$ dans lui-même qui n’est pas vide ainsi que son complément, le problème de savoir si une machine de Turing donnée calcule une fonction de F est indécidable sur tout sous-ensemble génériquement exponentiel de $I$.
Par ailleurs, on a deux résultats généraux:
Théorème. L'ensemble des langages formels génériquement calculables a mesure nulle.
Théorème. Il existe une hiérarchie infinie de classes de complexité génériques. Plus précisément, pour toute fonction de complexité propre $f$, on a Gen$(f)\subsetneq$Gen$(f^{3})$.

## Comparaison avec les travaux antérieurs

Deux notions proches existent.

### Temps presque polynomial

Un algorithme est dit en temps presque polynomial s'il s'arrête en temps $p(n)$ sur toutes les entrées de taille $n$, sauf pour $p(n)$ d'entre elles. Clairement, un tel algorithme est dans la classe GenP. La classe GenP contient des problèmes NP-complet, et pas les algorithmes en temps presque polynomial. Ainsi, les algorithmes en temps presque polynomial sont une famille plus petite que la classe GenP.

### Complexité en moyenne

La complexité générique est proche de la complexité en moyenne, avec quelques différences significatives.
La complexité générique mesure directement les performances d'un algorithme sur la plupart des données, alors que la complexité en moyenne cherche un équilibre entre instance faciles et difficiles. De plus, la complexité générique s'applique naturellement aussi aux problèmes indécidables. Revenons aux définitions.
Supposons que ${\mathcal {A}}$ est un algorithme dont la complexité en temps $T:I\to \mathbb {N}$ est polynomiale en moyenne sur $\mu$. Que peut-on en déduire sur le comportement de ${\mathcal {A}}$ sur des inputs générique?
Exemple. Soit $I$ l'ensemble des mots sur $\{0,1\}$, la taille d'un mot étant sa longueur. Soit $I_{n}$ l'ensemble des mots de longueur $n$, et soit $\mu _{n}$ la mesure équiprobable sur $I_{n}$. Si que $T(w)=n$ pour tous les mots de $I_{n}$ sauf un, et $T(w)=2^{2^{n}}$ pour ce mot exceptionnel, alors T est dans GenP, mais n'est pas poynomial en moyenne puisque le mot exceptionnel emporte tout.
Exemple. Soit $I$ comme avant, la taille étant la longueur. Soit $\mu (w)=2^{-2|w|-1}$ et $T(w)=2^{|w|}$. Alors T n'est pas dans GenP, et pourtant T est polynomial en moyenne'.
Dans ces deux exemples la complexité générique est plus proche du comportement sur des entrées typiques que de la complexité en moyenne. Dit de manière un peu sommaire, un algorithme qui est polynomial en moyenne n'a qu'une fraction sous-polynomiale de données pour lesquelles le temps est super-polynomial.