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[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éfinitionsModifier

Densité asymptotiqueModifier

Soit   un ensemble infini de données pour un problème algorithmique.

Définition. Une fonction taille sur   est une fonction  qui a une image infinie. La boule de rayon   est  .

Si les données sont codées comme mots sur un alphabet fini, la taille est fréquemment la longueur du mot.

Soit   un ensemble de distributions de probabilité, où    est une distribution de probabilité sur la boule  . Si les boules   sont finies, on peut prendre pour   la distribution uniforme, et c'est le cas le plus fréquent.

Définition. La densité asymptotique d'une partie   est

 ,

quand cette limite existe.

Quand les boules   sont finies et   est la mesure uniforme, on a

 

Dans ce cas, il est souvent commode d'utiliser les sphères   à la place des boules, et de définir

 .

Par le théorème de Stolz-Cesàro, la densité   existe si   existe, et dans ce cas les deux valeurs sont égales.

Definition. Une partie   est générique si   et elle est négligeable si  .   est exponentiellement (respectivement superpolynomialement) générique si la vitesse de convergence vers la limite   est exponentielle (respectivement. superpolynomiale). Une partie   est fortement générique s'il existe   telle que

 

pour presque tout entier naturel  .

Classes de complexité génériqueModifier

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  , on peut définir la classe Gen(f) correspondant à la complexité en temps   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 applicationsModifier

Problèmes en théorie combinatoire des groupesModifier

  • 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.
  • 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 PostModifier

Arithmétique de PresburgerModifier

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-completsModifier

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.

Fonctions à sens uniqueModifier

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é publiqueModifier

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 BrzozowskiModifier

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érauxModifier

Le théorème de Rice stipule que pour un ensemble   de fonction partielles calculables de   dans  , il est indécidable si la fonction calculée par une machine de machine de Turing donnée est une fonction de  , sauf dans les cas triviaux où   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   l'ensemble de toutes les machines de Turing. Pour un ensemble   de fonctions de   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  .

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  , on a Gen Gen .

Comparaison avec les travaux antérieursModifier

Deux notions proches existent.

Temps presque polynomialModifier

Un algorithme est dit en temps presque polynomial s'il s'arrête en temps   sur toutes les entrées de taille  , sauf pour   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 moyenneModifier

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   est un algorithme dont la complexité en temps   est polynomiale en moyenne sur  . Que peut-on en déduire sur la comportement de   sur des inputs générique?

Exemple. Soit   l'ensemble des mots sur  , la taille d'un mot étant sa longueur. Soit   l'ensemble des mots de longueur  , et soit   la mesure équiprobable sur  . Si que   pour tous les mots de   sauf un, et   pour ce mot exceptionnel, alors T est dans GenP, mais n'est pas poynomial en moyenne puisque le mot exceptionnel emporte tout.

Exemple. Soit   comme avant, la taille étant la longueur. Soit   et  . 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érencesModifier

  1. a b c et d Kapovich et al. 2003.
  2. Kapovich et al. 2005.
  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, no 1,‎ , p. 113-140 (Math Reviews 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, nos 5-6,‎ , p. 963–997 (Math Reviews 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, (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 J. Formal Logic, vol. 47,‎ , 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.
(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).

BibliographieModifier

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, no 2,‎ , p. 665-694 (Math Reviews 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, no 2,‎ , p. 343–359 (Math Reviews 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 », , xvi+183 p. (ISBN 978-3-7643-8826-3, Math Reviews 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 » (no 177), , xvi+385 p. (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 » (no 677), , 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, no 4,‎ , p. 307–318 (DOI 10.3233/COM-160060).