Principio de Yao - Yao's principle

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 determinista que funciona mejor contra 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 R aleatorio 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 sea ​​el conjunto de todos los posibles algoritmos deterministas que resuelven correctamente el problema. Para cualquier algoritmo y entrada , sea ​​el costo del algoritmo que se ejecuta en la entrada . ${\ Displaystyle {\ mathcal {X}}}$${\ Displaystyle {\ mathcal {A}}}$${\ Displaystyle a \ in {\ mathcal {A}}}$${\ Displaystyle x \ in {\ mathcal {X}}}$${\ Displaystyle c (a, x) \ geq 0}$${\ Displaystyle a}$${\ Displaystyle x}$

Sea una distribución de probabilidad sobre los algoritmos , y denotemos 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, ${\ Displaystyle p}$${\ Displaystyle {\ mathcal {A}}}$${\ Displaystyle A}$${\ Displaystyle p}$${\ Displaystyle q}$${\ Displaystyle {\ mathcal {X}}}$${\ Displaystyle X}$${\ Displaystyle q}$

${\ Displaystyle {\ underset {x \ in {\ mathcal {X}}} {\ max}} \ \ mathbf {E} [c (A, x)] \ geq {\ underset {a \ in {\ mathcal { A}}} {\ min}} \ \ mathbf {E} [c (a, X)].}$

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 . ${\ Displaystyle q}$

Prueba

Deja y . Tenemos ${\ Displaystyle C = {\ underset {x \ in {\ mathcal {X}}} {\ max}} \ \ mathbf {E} [c (A, x)]}$${\ Displaystyle D = {\ underset {a \ in {\ mathcal {A}}} {\ min}} \ \ mathbf {E} [c (a, X)]}$

${\ Displaystyle {\ begin {alineado} C & = \ sum _ {x} q_ {x} C \\ & \ geq \ sum _ {x} q_ {x} \ mathbf {E} [c (A, x)] \\ & = \ sum _ {x} q_ {x} \ sum _ {a} p_ {a} c (a, x) \\ & = \ sum _ {a} p_ {a} \ sum _ {x} q_ {x} c (a, x) \\ & = \ sum _ {a} p_ {a} \ mathbf {E} [c (a, X)] \\ & \ geq \ sum _ {a} p_ { a} D = D. \ end {alineado}}}$

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