En la teoría de la complejidad computacional , el principio de Yao (también llamado principio minimax de Yao o lema de Yao ) es una forma de demostrar límites inferiores en el peor de los casos de rendimiento de algoritmos aleatorios , comparándolos con algoritmos deterministas (no aleatorios). Afirma que, para cualquier algoritmo aleatorio, existe una distribución de probabilidad en las entradas del algoritmo, de modo que el costo esperado del algoritmo aleatorio en su entrada del peor caso es al menos tan grande como el costo del mejor algoritmo determinista en un entrada aleatoria de esta distribución. Por lo tanto, para establecer un límite inferior en el desempeño 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 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 de la variable seleccionada. 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 mixta para Alice. De manera similar, un algoritmo no aleatorio puede considerarse una estrategia pura para Alice. Según 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 haber elegido. La entrada en el peor de los casos contra la estrategia de Alice ha costado al menos tanto como la entrada elegida aleatoriamente de Bob combinada con la estrategia de Alice, que a su vez ha costado al menos tanto como la entrada elegida aleatoriamente de Bob combinada con cualquier estrategia pura.
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 que 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 del algoritmo ejecutado en la entrada .
Sea una distribución de probabilidad de los algoritmos y denotemos un algoritmo aleatorio elegido según . Sea una distribución de probabilidad sobre las entradas y denotemos una entrada aleatoria elegida de acuerdo con . Entonces,
Es decir, el costo esperado en el peor de los casos del algoritmo aleatorio es al menos el costo esperado del mejor algoritmo determinista frente a la distribución de entradas .
Deja y . Tenemos
Como se mencionó anteriormente, este teorema también puede verse como un caso muy especial del teorema Minimax .
![{\displaystyle {\underset {x\in {\mathcal {X}}}{\max }}\ \mathbf {E} [c(A,x)]\geq {\underset {a\in {\mathcal { A}}}{\min }}\ \mathbf {E} [c(a,X)].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a62477a26a957ebebe1df19662d1b1e6716a1c9)
![{\displaystyle C={\underset {x\in {\mathcal {X}}}{\max }}\ \mathbf {E} [c(A,x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/331a2baee308357e357f235a8fda94849afb67d3)
![{\displaystyle D={\underset {a\in {\mathcal {A}}}{\min }}\ \mathbf {E} [c(a,X)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a026426ebdec106d7c0d84d6f3ef12502b220fc)
![{\displaystyle {\begin{aligned}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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4c33ece53c235a13414a2c20c61c3584392e16d)