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

Le principe porte le nom d'Andrew Yao. On peut le prouver 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 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é, ne peut pas être inférieure à la complexité sur la pire des distributions d'entrées du meilleur algorithme déterministe pour cette distribution.

Plus formellement, et en suivant les notations de la section précédente : $\min _{B}\max _{x}C(B,x)=\max _{D}\min _{A}C(A,D)$.

Autrement dit pour tout algorithme B et toute distribution D, $\max _{x}C(B,x)\geq \min _{A}C(A,D)$.

Preuve

Par la théorie des jeux

On considère un jeu à deux joueurs, Alice et Bob où Alice définit l'algorithme et Bob choisit l'entrée. Pour une entrée et un algorithme on peut définir la complexité, qui devient le but du jeu : Bob gagne l'équivalent de la complexité et Alice le perd. C'est un jeu à somme nulle. 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.

Preuve directe

Pour toute distribution D et tout algorithme B, et en notant P la probabilité sur R, et $P_{D}$ la probabilité suivant la loi D:

$\max _{x}C(B,x)=\max _{x}\sum _{R}P(R)C(B,R,x)\geq \sum _{x}P_{D}(x)\sum _{R}P(R)C(B,R,x)=\sum _{R}\sum _{x}P_{D}(x)P(R)C(B,R,x)$.

Ainsi il doit exister un r, tel que $\max _{x}C(B,x)\geq \sum _{x}P_{D}(x)C(B,r,x)$, 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.

Applications

Le principe de Yao est notamment utilisé en test de propriété. Un exemple d'application est l'évaluation des arbres de jeux.

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.

Histoire

Andrew Yao

Andrew Yao a publié le principe et sa preuve dans l'article Probabilistic computations: toward a unified measure of complexity en 1977. 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 ».