Principe de Yao
En informatique théorique, le principe de Yao, ou principe min-max de Yao, est un théorème qui établit une relation générale entre les performances des algorithmes probabilistes et des algorithmes déterministes. Le principe porte le nom de l'informaticien Andrew Yao.
Le théorème montre notamment que pour connaître une borne inférieure sur le temps de calcul d'un algorithme probabiliste il suffit de s’intéresser aux performances des algorithmes déterministes sur des entrées aléatoires : si tout algorithme déterministe a une complexité élevée en moyenne sur une certaine distribution des entrées, alors tout algorithme probabiliste aura une complexité élevée sur sa pire entrée.
On peut démontrer le principe de Yao d'un point de vue de théorie des jeux, en utilisant le théorème minimax de von Neumann.
Contexte et notations
On mesure les performances des algorithmes avec des mesures, appelées « mesure de complexité » ou plus simplement « complexité ». Les mesures les plus classiques sont la complexité en temps et la complexité en espace. Le principe de Yao considère une mesure de complexité abstraite et fonctionne donc pour ces deux cas particuliers.
Un algorithme probabiliste est un algorithmes utilisant une source d'aléas, un générateur de bits aléatoires. On s’intéresse en particulier aux algorithmes de Las Vegas qui sont ceux qui donnent toujours une réponse exacte, mais dont le temps de calcul est une variable aléatoire. La complexité d'un tel algorithme est l'espérance de la complexité de l’algorithme.
Un algorithme déterministe n'utilise pas de bits aléatoires, mais on peut par contre mesurer sa complexité en moyenne sur une distribution d'entrées. Il s'agit, sachant que les entrées suivent telle loi de probabilité, de savoir quel va être le temps de calcul de l'algorithme si on moyenne sur toutes les entrées selon cette distribution. On parle de complexité distributionnelle.
Étant donné un algorithme déterministe A, on peut noter C(A,x), la complexité de l'algorithme sur l'entrée x. Pour un algorithme probabiliste B, on note C(B,R,x) la complexité de l’algorithme sur l'entrée x, avec les bits aléatoires R. On peut ensuite définir, pour un algorithme probabiliste, C(B,x), l'espérance de C(B,R,x) ; et pour un algorithme déterministe A et une distribution D, C(A,D), l'espérance de C(A,x) quand x suit D.
Énoncé
Le théorème donne pour tout problème algorithmique, une borne inférieure sur l'espérance de la complexité d'un algorithme probabiliste. Cette complexité doit être plus supérieure à la complexité sur la pire distribution d'entrées du meilleur algorithme déterministe pour cette distribution.
Plus formellement, en fixant un problème algorithmique, et en suivant les notations de la section précédente[1] : où dans , le minimum est calculé pour tout algorithme probabiliste B qui décide le problème algorithmique, dans , le maximum est calculé pour toute entrée x, dans , le maximum est calculé pour distribution D sur les entrées, dans , le minimum est calculé pour tout algorithmique déterministe A qui décide le problème algorithmique.
Autrement dit pour tout algorithme probabiliste B et toute distribution D, .
Preuve
Par la théorie des jeux
On définit le jeu à somme nulle à deux joueurs suivant. Les deux joueurs sont Alice et Bob. Alice choisit un algorithme probabiliste B et Bob choisit l'entrée x. Étant donné un algorithmique probabiliste B, une entrée x choisis, le gain du jeu pour Bob est la complexité C(B, x). Autrement dit, Bob gagne C(B, x) et Alice perd C(B, x). En utilisant le théorème minimax de von Neumann, on obtient qu'il existe un équilibre pour les stratégies probabilistes, ce qui est équivalent au principe de Yao[2].
Preuve directe
Pour toute distribution D et tout algorithme B, et en notant P la probabilité sur R, et la probabilité suivant la loi D:
.
Ainsi il doit exister un r, tel que , et B sur cette chaîne r' donne un algorithme déterministe A qui satisfait l'inégalité.
Variante
On peut écrire un analogue du principe de Yao pour les algorithmes de Monte-Carlo[2],[3].
Applications
Le principe de Yao est notamment utilisé en test de propriété[4]. Un exemple d'application est l'évaluation des arbres de jeux[2].
De façon plus générale le principe est utilisé pour prouver des bornes inférieures sur des algorithmes probabiliste. La technique consiste à trouver une distribution des entrées qui est difficile pour tout algorithme déterministe puis à transférer la borne inférieure[5].
Histoire
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Andrew_Yao.jpg/220px-Andrew_Yao.jpg)
Andrew Yao a publié le principe et sa preuve dans l'article Probabilistic computations: toward a unified measure of complexity en 1977[3]. Il a obtenu le prix Turing en 2000 pour ses travaux en informatique théorique et notamment pour ce principe décrit comme «une technique fondamentale dans l'étude des algorithmes probabilistes, ayant eu des applications dans d'autres domaines comme le test de propriété et la théorie de l'apprentissage automatique »[6].
Notes et références
- ↑ Elena Grigorescu, « Current Topics in Theoretical CS: Lecture 20, 1: Yao's Principle », sur université Purdue, .
- ↑ a b et c (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge, New York et Melbourne, Cambridge University Press, (réimpr. 1997, 2000), 1re éd., 476 p. (ISBN 978-0-521-47465-8, lire en ligne), chap. 2.2.2 (« The minimax principle: Yao's technique »), p. 35.
- ↑ a et b Andrew Chi-Chih Yao, « Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract) », dans 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977, (DOI 10.1109/SFCS.1977.24), p. 222-227.
- ↑ On peut trouver trois applications dans le document suivant : Sofya Raskhodnikov, « Lecture 5: Yao's Minimax Principle », .
- ↑ (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 12.5 (« Lower bounds on Randomized complexity »), p. 229
- ↑ « A. M. Turing Award Winners: Andrew Chi-Chih Yao », sur ACM.
Portail de l'informatique théorique