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 caso no es mejor que el costo esperado para una distribución de probabilidad del peor caso en las entradas de el algoritmo deterministaque funciona mejor con esa distribución. Por lo tanto, para establecer un límite inferior en el rendimiento de los algoritmos aleatorios, es suficiente encontrar una distribución apropiada de entradas difíciles y demostrar 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 se puede interpretar en términos de la teoría del juego , a través de un juego de suma cero para dos jugadores en el que un jugador, Alice , selecciona un algoritmo determinista, el otro jugador, Bob, selecciona una entrada y la recompensa es el costo de la selección. algoritmo en la entrada seleccionada. Cualquier algoritmo aleatorio R puede interpretarse como una elección aleatoria entre algoritmos deterministas y, por tanto, como una estrategia para Alice. Según el teorema del 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 en las entradas tal que el costo esperado de R en esa distribución (y por lo tanto también el costo esperado en el peor de los casos de R ) no es mejor que el costo esperado de cualquier algoritmo determinista único contra la misma distribución.
Declaración
La siguiente formulación establece el principio para 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 limitados pero pueden ser incorrectos en algunas entradas.
Considere un problema sobre las entradas , y deja ser el conjunto de todos los posibles algoritmos deterministas que resuelven correctamente el problema. Para cualquier algoritmo y entrada , dejar ser el costo del algoritmo ejecutar en entrada .
Dejar ser una distribución de probabilidad sobre los algoritmos , y deja denotar un algoritmo aleatorio elegido de acuerdo con . Dejar ser una distribución de probabilidad sobre las entradas , y deja denotar una entrada aleatoria elegida de acuerdo con . Luego,
Es decir, el costo esperado en el peor de los casos del algoritmo aleatorizado es al menos el costo esperado del mejor algoritmo determinista contra la distribución de entrada. .
Prueba
Dejar y . Tenemos
Como se mencionó anteriormente, este teorema también puede verse como un caso muy especial del teorema Minimax .
Referencias
- Borodin, Allan ; El-Yaniv, Ran (2005), "8.3 Principio de Yao: una técnica para obtener límites inferiores" , Computación en línea y análisis competitivo , Cambridge University Press, págs. 115-120, ISBN 9780521619462
- Yao, Andrew (1977), "Cálculos probabilísticos: Hacia una medida unificada de complejidad", Actas del 18o Simposio IEEE sobre Fundamentos de la Ciencia de la Computación (FOCS) , págs. 222-227, doi : 10.1109 / SFCS.1977.24
enlaces externos
- Fortnow, Lance (16 de octubre de 2006), "Teoremas favoritos: principio de Yao" , Complejidad computacional