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 XX^e siècle. La notion de complexité générique a été introduit en 2003 dans des articles de Kapovich, Miasnikov, Schupp et Shpilrain^[1]^,^[2]. 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^[3]. Les livres de Miasnikov, Shpilrain et Ushakov^[4]^,^[5] traitent principalement des résultats des auteurs relativement à la cryptographie.

Définitions modifier

Densité asymptotique modifier

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 modifier

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 modifier

Problèmes en théorie combinatoire des groupes modifier

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^[1].

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^[6].

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^[7].

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^[8]. Pour certains groupes, des résultats plus précis ont été obtenus par Diekert et ses coauteurs^[9]

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

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^[10].

Le problème de correspondance de Post est dans ExpGenP^[3].

Arithmétique de Presburger modifier

Le problème de décision pour l'arithmétique de Presburger admet un borne inférieure doublement exponentielle dans le pire des cas^[11] 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^[12].

Problèmes NP-complets modifier

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^[3].

Le subset sum problem est dans la classe GenP^[3].

Fonctions à sens unique modifier

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

Cryptographie à clé publique modifier

Tout un ensemble de travaux^[14]^,^[15]^,^[16] 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^[17] 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 modifier

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^[18]. Dans certains cas, on peut en analyser la complexité en moyenne^[19].

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

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^[20]. 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^[1]. L'ensemble des langages formels génériquement calculables a mesure nulle.

Théorème^[1]. 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 modifier

Deux notions proches existent.

Temps presque polynomial modifier

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 modifier

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.

Notes et références modifier

↑ ^{a b c et d} Kapovich et al. 2003.
↑ Kapovich et al. 2005.
↑ ^{a b c et d} R. Gilman, A. G. Miasnikov, A. D. Myasnikov, et A. Ushakov, Report on generic case complexity, Herald of Omsk University, Special Issue, 2007, 103–110.
↑ Miasnikov, Shpilrain et Ushakov 2008.
↑ Miasnikov, Shpilrain et Ushakov 2011.
↑ Robert Gilman, « Hard problems in group theory », International Conference on Geometric and Combinatorial Methods in Group Theory and Semigroup Theory, 18 mai 2009.
↑ Ilya Kapovich, Paul Schupp et Vladimir Shpilrain, « Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups », Pacific J. Math, vol. 223, n^o 1,‎ 2006, p. 113-140 (MR 2007e:20068, arXiv math.GR/0303386).
↑ Alexandre V. Borovik, Alexei G. Myasnikov et Vladimir N. Remeslennikov, « Generic complexity of the conjugacy problem in HNN-extensions and algorithmic stratification of Miller's groups », Internat. J. Algebra Comput., vol. 17, n^os 5-6,‎ 2007, p. 963–997 (MR 2008m:20046, arXiv 0903.3754).
↑ Volker Diekert, Alexei G. Myasnikov et Armin Weiß, « Conjugacy in Baumslag's group, generic case complexity, and division in power circuits », dans LATIN 2014. Latin American Theoretical INformatics Symposium, Montévidéo, 31 mars - 4 avril 2014 (arXiv 1309.5314).
↑ Joel David Hamkins et Alexei G. Miasnikov, « The halting problem is decidable on a set of asymptotic probability one », Notre Dame Journal of Formal Logic, vol. 47,‎ 2006, p. 515–524 (arXiv math/0504351).
↑ M. J. Fischer et M. O. Rabin, Super-Exponential Complexity of Presburger Arithmetic, Proceedings of the SIAM-AMS Symposium in Applied Mathematics 7 (1974) 2741.
↑ A. Rybalov, Generic complexity of Presburger arithmetic, 356–361 in Second International Computer Science Symposium in Russia, CSR 2007, Lecture Notes in Computer Science 4649, Springer 2007.
↑ Alex D. Myasnikov, Generic Complexity and One-Way Functions, Groups, Complexity and Cryptography, 1, (2009), 13–31.
↑ R. Gilman, Alexei G. Miasnikov, Alex D. Myasnikov, et Alexander Ushakov, New developments in commutator key exchange, Proc. First Int. Conf. on Symbolic Computation and Cryptography (SCC-2008), Beijing, 2008.
↑ Alexei. G. Myasnikov, V. Shpilrain, Alexander Ushakov, A practical attack on a braid group based cryptographic protocol, in Lecture Notes in Computer Science, 3621, Springer Verlag, 2005, 86–96.
↑ Alex D. Myasnikov, et Alexander Ushakov, Length based attack and braid groups: cryptanalysis of Anshel–Anshel–Goldfeld key exchange protocol, in Public Key Cryptography PKC 2007, 76–88, Lecture Notes in Comput. Sci., 4450, Springer, Berlin, 2007.
↑ Alexei G. Miasnikov et Alexander Ushakov, Random subgroups and analysis of the length-based and quotient attacks, Journal of Mathematical Cryptology, 2 (2008), 29–61.
↑ Sven De Felice et Cyril Nicaud, « Brzozowski algorithm is generically super-polynomial for deterministic automata ». Developments in Language Theory (2013), p. 179–190.
↑ Sven De Felice et Cyril Nicaud. « On the Average Complexity of Brzozowski's Algorithm for Deterministic Automata with a Small Number of Final States ». Developments in Language Theory (2014), Ekaterinenburg, Russie.
↑ Alexei G. Miasnikov and A. Rybalov, Generic complexity of undecidable problems, J. Symbolic Logic 73 (2008), 656–673.

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Generic-case complexity » (voir la liste des auteurs).

Bibliographie modifier

Articles fondateurs

Ilya Kapovich, Alexei G. Miasnikov, Paul Schupp et Vladimir Shpilrain, « Generic-case complexity, decision problems in group theory, and random walks », J. Algebra, vol. 264, n^o 2,‎ 2003, p. 665-694 (MR 2005m:20080, arXiv math/0203239).
Ilya Kapovich, Alexei G. Miasnikov, Paul Schupp et Vladimir Shpilrain, « Average-case complexity and decision problems in group theory », Adv. Math, vol. 190, n^o 2,‎ 2005, p. 343–359 (MR 2005i:20053, arXiv math/0206273).

Ouvrages de référence

Alexei G. Miasnikov, Vladimir Shpilrain et Alexander Ushakov, Group-based Cryptography, Bâle, Birkhäuser Verlag, coll. « Advanced Courses in Mathematics - CRM Barcelona », 2008, xvi+183 (ISBN 978-3-7643-8826-3, MR 2009d:94098, zbMATH 1248.94004, lire en ligne).
Alexei G. Miasnikov, Vladimir Shpilrain et Alexander Ushakov, Non-commutative cryptography and complexity of group-theoretic problems : With an appendix by Natalia Mosina, Providence, RI, American Mathematical Society, coll. « Mathematical Surveys and Monographs » (n^o 177), 2011, xvi+385 (ISBN 978-0-8218-5360-3, zbMATH 1248.94006, lire en ligne).

Articles récents

Frédérique Bassino, Cyril Nicaud et Pascal Weil, « Generic properties of subgroups of free groups and finite presentations », dans Delaram Kahrobaei, Bren Cavallo et David Garber (éditeurs), Algebra and Computer Science, American Mathematical Society, coll. « Contemporary Mathematics » (n^o 677), 2016, 229 p. (ISBN 978-1-4704-2303-2, arXiv 1507.01088, présentation en ligne), p. 1-44.
Alexei Miasnikov et Paul Schupp, « Computational complexity and the conjugacy problem », Computability, vol. 6, n^o 4,‎ 2017, p. 307–318 (DOI 10.3233/COM-160060).

Portail de l'informatique théorique

[KMSS-1] {a b c et d} Kapovich et al. 2003.

[KMSS2-2] Kapovich et al. 2005.

[Omsk-3] {a b c et d} R. Gilman, A. G. Miasnikov, A. D. Myasnikov, et A. Ushakov, Report on generic case complexity, Herald of Omsk University, Special Issue, 2007, 103–110.

[4] Miasnikov, Shpilrain et Ushakov 2008.

[5] Miasnikov, Shpilrain et Ushakov 2011.

[6] Robert Gilman, « Hard problems in group theory », International Conference on Geometric and Combinatorial Methods in Group Theory and Semigroup Theory, 18 mai 2009.

[7] Ilya Kapovich, Paul Schupp et Vladimir Shpilrain, « Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups », Pacific J. Math, vol. 223, n^o 1,‎ 2006, p. 113-140 (MR 2007e:20068, arXiv math.GR/0303386).

[8] Alexandre V. Borovik, Alexei G. Myasnikov et Vladimir N. Remeslennikov, « Generic complexity of the conjugacy problem in HNN-extensions and algorithmic stratification of Miller's groups », Internat. J. Algebra Comput., vol. 17, n^os 5-6,‎ 2007, p. 963–997 (MR 2008m:20046, arXiv 0903.3754).

[9] Volker Diekert, Alexei G. Myasnikov et Armin Weiß, « Conjugacy in Baumslag's group, generic case complexity, and division in power circuits », dans LATIN 2014. Latin American Theoretical INformatics Symposium, Montévidéo, 31 mars - 4 avril 2014 (arXiv 1309.5314).

[10] Joel David Hamkins et Alexei G. Miasnikov, « The halting problem is decidable on a set of asymptotic probability one », Notre Dame Journal of Formal Logic, vol. 47,‎ 2006, p. 515–524 (arXiv math/0504351).

[11] M. J. Fischer et M. O. Rabin, Super-Exponential Complexity of Presburger Arithmetic, Proceedings of the SIAM-AMS Symposium in Applied Mathematics 7 (1974) 2741.

[12] A. Rybalov, Generic complexity of Presburger arithmetic, 356–361 in Second International Computer Science Symposium in Russia, CSR 2007, Lecture Notes in Computer Science 4649, Springer 2007.

[13] Alex D. Myasnikov, Generic Complexity and One-Way Functions, Groups, Complexity and Cryptography, 1, (2009), 13–31.

[14] R. Gilman, Alexei G. Miasnikov, Alex D. Myasnikov, et Alexander Ushakov, New developments in commutator key exchange, Proc. First Int. Conf. on Symbolic Computation and Cryptography (SCC-2008), Beijing, 2008.

[15] Alexei. G. Myasnikov, V. Shpilrain, Alexander Ushakov, A practical attack on a braid group based cryptographic protocol, in Lecture Notes in Computer Science, 3621, Springer Verlag, 2005, 86–96.

[16] Alex D. Myasnikov, et Alexander Ushakov, Length based attack and braid groups: cryptanalysis of Anshel–Anshel–Goldfeld key exchange protocol, in Public Key Cryptography PKC 2007, 76–88, Lecture Notes in Comput. Sci., 4450, Springer, Berlin, 2007.

[17] Alexei G. Miasnikov et Alexander Ushakov, Random subgroups and analysis of the length-based and quotient attacks, Journal of Mathematical Cryptology, 2 (2008), 29–61.

[18] Sven De Felice et Cyril Nicaud, « Brzozowski algorithm is generically super-polynomial for deterministic automata ». Developments in Language Theory (2013), p. 179–190.

[19] Sven De Felice et Cyril Nicaud. « On the Average Complexity of Brzozowski's Algorithm for Deterministic Automata with a Small Number of Final States ». Developments in Language Theory (2014), Ekaterinenburg, Russie.

[20] Alexei G. Miasnikov and A. Rybalov, Generic complexity of undecidable problems, J. Symbolic Logic 73 (2008), 656–673.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]