el principio de yao

En la teoría de la complejidad computacional , el principio de Yao (también llamado principio minimax de Yao o lema de Yao ) establece que el costo esperado de un algoritmo aleatorio en la entrada del peor de los casos no es mejor que el costo esperado para una distribución de probabilidad del peor de los casos en las entradas de el algoritmo deterministaque funciona mejor contra esa distribución. Por lo tanto, para establecer un límite inferior en el rendimiento de los algoritmos aleatorios, basta con encontrar una distribución adecuada de entradas difíciles y probar que ningún algoritmo determinista puede funcionar bien contra esa distribución. Este principio lleva el nombre de Andrew Yao , quien lo propuso por primera vez.

El principio de Yao puede interpretarse en términos de teoría de juegos , a través de un juego de suma cero de dos jugadores en el que un jugador, Alice , selecciona un algoritmo determinista, el otro jugador, Bob, selecciona una entrada y el pago es el costo del seleccionado. algoritmo en la entrada seleccionada. Cualquier algoritmo aleatorio R puede interpretarse como una elección aleatoria entre algoritmos deterministas y, por lo tanto, como una estrategia para Alice. Por el teorema minimax de von Neumann , Bob tiene una estrategia aleatoria que funciona al menos tan bien contra R como contra la mejor estrategia pura que Alice podría elegir; es decir, la estrategia de Bob define una distribución de las entradas tal que el costo esperado de Ren esa distribución (y por lo tanto también el costo esperado de R en el peor de los casos ) no es mejor que el costo esperado de cualquier algoritmo determinista único contra la misma distribución.

La siguiente formulación establece el principio de los algoritmos aleatorios de Las Vegas , es decir, distribuciones sobre algoritmos deterministas que son correctos en cada entrada pero tienen costos variables. Es sencillo adaptar el principio a los algoritmos de Monte Carlo , es decir, distribuciones sobre algoritmos deterministas que tienen costos acotados pero pueden ser incorrectos en algunas entradas.

Considere un problema sobre las entradas y sea el conjunto de todos los algoritmos deterministas posibles que resuelven correctamente el problema. Para cualquier algoritmo y entrada , sea el costo de la ejecución del algoritmo en la entrada . ${\mathcal {X}}$ ${\mathcal {A}}$ $a\in {\mathcal {A}}$ $x\in {\mathcal {X}}$ ${\ estilo de visualización c (a, x) \ geq 0}$ ${\ estilo de visualización a}$ ${\ estilo de visualización x}$

Sea una distribución de probabilidad sobre los algoritmos y denote un algoritmo aleatorio elegido de acuerdo con . Sea una distribución de probabilidad sobre las entradas y denote una entrada aleatoria elegida de acuerdo con . Luego, ${\ estilo de visualización p}$ ${\mathcal {A}}$ ${\ estilo de visualización A}$ ${\ estilo de visualización p}$ ${\ estilo de visualización q}$ ${\mathcal {X}}$ ${\ estilo de visualización X}$ ${\ estilo de visualización q}$

Es decir, el costo esperado del algoritmo aleatorio en el peor de los casos es al menos el costo esperado del mejor algoritmo determinista frente a la distribución de entrada . ${\ estilo de visualización q}$