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 ) relaciona el rendimiento de los algoritmos aleatorios con el de los algoritmos deterministas (no aleatorios). Este principio establece que, para ciertas clases de algoritmos y ciertas medidas de su rendimiento, las dos cantidades siguientes son iguales:

El rendimiento óptimo que puede obtener un algoritmo determinista sobre una entrada aleatoria (su complejidad en el caso promedio ), para una distribución de probabilidad sobre las entradas elegida para que sea lo más difícil posible y para un algoritmo elegido para que funcione lo mejor posible contra esa distribución.
El rendimiento óptimo que puede obtener un algoritmo aleatorio en una entrada determinista (su complejidad esperada), para un algoritmo elegido para tener el mejor rendimiento en sus peores casos de entrada, y la peor entrada del algoritmo.

El principio de Yao se utiliza a menudo para demostrar las limitaciones en el rendimiento de los algoritmos aleatorios, al encontrar una distribución de probabilidad en las entradas que resulta difícil para los algoritmos deterministas, e inferir que los algoritmos aleatorios tienen la misma limitación en su rendimiento en el peor de los casos. ^{[ 1 ]}

Este principio recibe su nombre de Andrew Yao , quien lo propuso por primera vez en un artículo de 1977. ^{[ 2 ]} Está estrechamente relacionado con el teorema minimax en la teoría de juegos de suma cero y con la teoría de dualidad de programas lineales .

Formulación

El principio de Yao se formula en términos de una medida de costo real arbitraria. $c(A,x)$ de un algoritmo $A$ en una entrada $x$ , como su tiempo de ejecución, para el cual se desea estudiar el valor esperado sobre algoritmos aleatorios y entradas aleatorias. Los algoritmos utilizados en esta medida de costo se extraen de un conjunto finito ${\mathcal {A}}$ de algoritmos deterministas; una forma típica de hacer que un problema tenga solo un conjunto finito de algoritmos es restringir sus entradas a un solo tamaño. Las entradas también deben extraerse de un conjunto finito. ${\mathcal {X}}$ , que puede hacerse finita de la misma manera. Entonces, cada distribución de probabilidad sobre ${\mathcal {A}}$ corresponde a un algoritmo aleatorio que primero hace una elección aleatoria de ${\mathcal {A}}$ de acuerdo con esa distribución y luego sigue el algoritmo elegido; de esta manera, la clase de algoritmos aleatorios para el mismo problema puede modelarse como la clase ${\mathcal {R}}$ de todas las distribuciones de probabilidad sobre ${\mathcal {A}}$ Finalmente, la formulación del principio de Yao involucra la clase de todas las distribuciones de probabilidad en las entradas en ${\mathcal {X}}$ , denotado como ${\mathcal {D}}$ . Entonces, el principio de Yao establece que: ^{[ 1 ]}

$\max _{D\in {\mathcal {D}}}\min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]=\min _{R\in {\mathcal {R}}}\max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)].$

Aquí, $\mathbb {E}$ es la notación para el valor esperado, y $x\sim D$ significa que $x$ es una variable aleatoria distribuida según $D$ El lado izquierdo de la fórmula proporciona el rendimiento óptimo que se puede obtener mediante un algoritmo determinista. $A$ en una entrada aleatoria $x$ (su complejidad en el caso promedio ), para una distribución de probabilidad $D$ en entradas que es lo más difícil posible y con $A$ siendo el algoritmo que mejor se desempeña contra $D$ El lado derecho muestra el rendimiento óptimo que se puede obtener mediante un algoritmo aleatorio. $R$ en una entrada determinista $x$ (su complejidad esperada), cuando $R$ tiene el mejor rendimiento en sus peores casos de entrada, y cuando $x$ es una entrada de peor caso para $R$ . ^{[ 1 ]} La finitud de ${\mathcal {A}}$ y ${\mathcal {X}}$ permite ${\mathcal {D}}$ y ${\mathcal {R}}$ para ser interpretados como símplices de vectores de probabilidad , ^{[ 3 ]} cuya compacidad implica que los mínimos y máximos en estas fórmulas existen. ^{[ 4 ]}

Otra versión del principio de Yao lo debilita, transformándolo de una igualdad a una desigualdad, pero al mismo tiempo lo generaliza al relajar el requisito de que los algoritmos y las entradas provengan de un conjunto finito. La dirección de la desigualdad permite utilizarlo cuando se ha demostrado que una distribución de entrada específica es difícil para los algoritmos deterministas, convirtiéndolo en una cota inferior del coste de todos los algoritmos aleatorios. En esta versión, para cada distribución de entrada $D\in {\mathcal {D}}$ y para cada algoritmo aleatorio $R$ en ${\mathcal {R}}$ , ^{[ 1 ]} $\min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]\leq \max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)].$ Es decir, el mejor desempeño determinista posible frente a la distribución. $D$ es un límite inferior para el rendimiento de cada algoritmo aleatorio $R$ frente a su peor caso de entrada. Esta versión del principio de Yao se puede demostrar a través de la cadena de desigualdades. $\min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]\leq \mathbb {E} _{x\sim D}[c(R,x)]\leq \max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)],$ cada uno de los cuales puede demostrarse utilizando únicamente la linealidad de la esperanza y el principio de que $\min \leq \mathbb {E} \leq \max$ para todas las distribuciones. Al evitar la maximización y la minimización sobre ${\mathcal {D}}$ y ${\mathcal {R}}$ , esta versión del principio de Yao puede aplicarse en algunos casos donde ${\mathcal {X}}$ o ${\mathcal {A}}$ no son finitos. ^{[ 5 ]} Aunque esta dirección de desigualdad es la necesaria para demostrar cotas inferiores en algoritmos aleatorios, la versión de igualdad del principio de Yao, cuando está disponible, también puede ser útil en estas demostraciones. La igualdad del principio implica que no hay pérdida de generalidad al usar el principio para demostrar cotas inferiores: cualquiera que sea el mejor algoritmo aleatorio real, existe alguna distribución de entrada a través de la cual se puede demostrar una cota inferior correspondiente en su complejidad. ^{[ 6 ]}

Aplicaciones y ejemplos

complejidad temporal

Cuando el costo $c$ denota el tiempo de ejecución de un algoritmo. El principio de Yao establece que el mejor tiempo de ejecución posible de un algoritmo determinista, en una distribución de entrada estricta, proporciona una cota inferior para el tiempo esperado de cualquier algoritmo de Las Vegas en su peor caso de entrada. Aquí, un algoritmo de Las Vegas es un algoritmo aleatorio cuyo tiempo de ejecución puede variar, pero cuyo resultado siempre es correcto. ^{[ 7 ]}^{[ 8 ]} Por ejemplo, esta forma del principio de Yao se ha utilizado para demostrar la optimalidad de ciertos algoritmos de búsqueda en árbol de Monte Carlo para la evaluación exacta de árboles de juego . ^{[ 8 ]}

Comparaciones

La complejidad temporal de los algoritmos de ordenación y selección basados en comparaciones se estudia a menudo utilizando el número de comparaciones entre pares de elementos de datos como una aproximación del tiempo total. Cuando estos problemas se consideran sobre un conjunto fijo de elementos, sus entradas pueden expresarse como permutaciones y un algoritmo determinista puede expresarse como un árbol de decisión . De esta manera, tanto las entradas como los algoritmos forman conjuntos finitos, como exige el principio de Yao. Un argumento de simetrización identifica las distribuciones de entrada más difíciles: son las permutaciones aleatorias , las distribuciones en $n$ Elementos distintos para los cuales todas las permutaciones son igualmente probables. Esto se debe a que, si cualquier otra distribución fuera la más difícil, promediarla con todas las permutaciones de la misma distribución difícil sería igualmente difícil y produciría la distribución para una permutación aleatoria. El principio de Yao extiende los límites inferiores para el número promedio de casos de comparaciones realizadas por algoritmos deterministas, para permutaciones aleatorias, al análisis del peor caso de algoritmos de comparación aleatorios. ^{[ 2 ]}

Un ejemplo dado por Yao es el análisis de algoritmos para encontrar el $k$ el mayor de un conjunto dado de $n$ valores, el problema de selección. ^{[ 2 ]} Posteriormente al trabajo de Yao, Walter Cunto e Ian Munro demostraron que, para permutaciones aleatorias, cualquier algoritmo determinista debe realizar al menos $n+\min(k,nk)-O(1)$ comparaciones esperadas. ^{[ 9 ]} Según el principio de Yao, los algoritmos aleatorios deben realizar el mismo número de comparaciones en su entrada del peor caso. ^{[ 10 ]} El algoritmo de Floyd-Rivest se encuentra dentro $O({\sqrt {n\log n}})$ comparaciones de este límite. ^{[ 11 ]}

Evasión de las propiedades de los grafos

Otra de las aplicaciones originales de Yao de su principio fue a la evasión de las propiedades de los grafos , el número de pruebas de adyacencia de pares de vértices necesarias para determinar si un grafo tiene una propiedad dada, cuando el único acceso al grafo es a través de dichas pruebas. ^{[ 2 ]} Richard M. Karp conjeturó que todo algoritmo aleatorio para toda propiedad monótona no trivial de un grafo (una propiedad que permanece verdadera para cada subgrafo de un grafo con la propiedad) requiere un número cuadrático de pruebas, pero solo se han demostrado cotas más débiles. ^{[ 12 ]}

Como afirmó Yao, para propiedades de grafos que son verdaderas para el grafo vacío pero falsas para algún otro grafo en $n$ vértices con un número limitado $s$ de aristas, un algoritmo aleatorio debe sondear un número cuadrático de pares de vértices. Por ejemplo, para la propiedad de ser un grafo planar , $s=9$ porque el grafo de utilidad de 9 aristas no es planar. Más precisamente, Yao afirma que para estas propiedades, al menos $\left({\tfrac {1}{2}}-p\right){\tfrac {1}{s}}{\tbinom {n}{2}}$ Se necesitan pruebas, para cada $\varepsilon >0$ , para que un algoritmo aleatorio tenga una probabilidad como máximo $p$ de cometer un error. Yao también utilizó este método para demostrar que se necesitan cuadráticamente muchas consultas para las propiedades de contener un árbol o clique dado como subgrafo, de contener un emparejamiento perfecto y de contener un ciclo hamiltoniano , para probabilidades de error constantes suficientemente pequeñas. ^{[ 2 ]}

Optimización de caja negra

En la optimización de caja negra , el problema consiste en determinar el valor mínimo o máximo de una función, de una clase dada de funciones, accesibles únicamente mediante llamadas a la función sobre argumentos de un dominio finito. En este caso, el costo a optimizar es el número de llamadas. El principio de Yao se ha descrito como "el único método disponible para demostrar cotas inferiores para todas las heurísticas de búsqueda aleatoria para clases de problemas seleccionadas". ^{[ 13 ]} Los resultados que se pueden demostrar de esta manera incluyen los siguientes:

Para funciones booleanas en $n$ cadenas binarias de bits que comprueban si la entrada es igual a alguna cadena fija pero desconocida, el número óptimo esperado de llamadas a funciones necesarias para encontrar la cadena desconocida es $2^{n-1}+{\tfrac {1}{2}}$ Esto se puede lograr mediante una función que prueba cadenas en un orden aleatorio, y se demostró que es óptima al usar el principio de Yao en una distribución de entrada que elige una función aleatoria uniforme de esta clase. ^{[ 13 ]}
Una función unimodal $f$ de $n$ La conversión de cadenas binarias de bits a números reales se define mediante la siguiente propiedad: Para cada cadena de entrada $x$ , cualquiera $f(x)$ es el valor máximo único de $f$ , o $x$ se puede cambiar en un solo bit a una cadena $y$ con un valor mayor. Por lo tanto, una búsqueda local que cambia un bit a la vez cuando esto produce un valor mayor siempre encontrará finalmente el valor máximo. Dicha búsqueda puede tomar exponencialmente muchos pasos, pero no es posible nada significativamente mejor. Para cualquier algoritmo aleatorio que realice $2^{o(n)}$ consultas, alguna función de esta clase hará que el algoritmo tenga una probabilidad exponencialmente pequeña de encontrar el máximo. ^{[ 13 ]}

Complejidad de la comunicación

En la complejidad de la comunicación , un algoritmo describe un protocolo de comunicación entre dos o más partes, y su costo puede ser el número de bits o mensajes transmitidos entre ellas. En este caso, el principio de Yao describe una igualdad entre la complejidad promedio de los protocolos de comunicación deterministas, con una distribución de entrada que representa el peor caso para el problema, y la complejidad de comunicación esperada de los protocolos aleatorios con sus entradas en el peor caso. ^{[ 6 ]}^{[ 14 ]}

Un ejemplo descrito por Avi Wigderson (basado en un artículo de Manu Viola) es la complejidad de la comunicación para dos partes, cada una de las cuales tiene $n$ valores de entrada de bits, para determinar qué valor es mayor. Para protocolos de comunicación deterministas, nada mejor que $n$ Es posible la comunicación de bits, fácilmente lograda por una parte enviando toda su entrada a la otra. Sin embargo, las partes con una fuente compartida de aleatoriedad y una probabilidad de error fija pueden intercambiar funciones hash de 1 bit de prefijos de la entrada para realizar una búsqueda binaria ruidosa de la primera posición donde sus entradas difieren, logrando $O(\log n)$ bits de comunicación. Esto se encuentra dentro de un factor constante de óptimo, como se puede demostrar mediante el principio de Yao con una distribución de entrada que elige la posición de la primera diferencia de forma uniforme y aleatoria, y luego elige cadenas aleatorias para el prefijo compartido hasta esa posición y el resto de las entradas después de esa posición. ^{[ 6 ]}^{[ 15 ]}

Algoritmos en línea

El principio de Yao también se ha aplicado a la razón de competitividad de los algoritmos en línea . Un algoritmo en línea debe responder a una secuencia de solicitudes, sin conocimiento de las solicitudes futuras, incurriendo en un costo o beneficio por solicitud según sus decisiones. La razón de competitividad es la relación entre su costo o beneficio y el valor que podría obtener un algoritmo fuera de línea con acceso al conocimiento de todas las solicitudes futuras, para una secuencia de solicitudes en el peor de los casos que hace que esta razón se aleje lo más posible de uno. Aquí, se debe tener cuidado al formular la razón con el rendimiento del algoritmo en el numerador y el rendimiento óptimo de un algoritmo fuera de línea en el denominador, de modo que la medida de costo pueda formularse como un valor esperado en lugar de como el recíproco de un valor esperado. ^{[ 5 ]}

Un ejemplo dado por Borodin y El-Yaniv (2005) se refiere a los algoritmos de reemplazo de páginas , que responden a las solicitudes de páginas de memoria de la computadora mediante el uso de una caché de $k$ páginas, para un parámetro dado $k$ . Si una solicitud coincide con una página en caché, no tiene costo; de lo contrario, una de las páginas en caché debe ser reemplazada por la página solicitada, con un costo de una falla de página . Se puede generar una distribución difícil de secuencias de solicitudes para este modelo eligiendo cada solicitud uniformemente al azar de un conjunto de $k+1$ páginas. Cualquier algoritmo en línea determinista tiene ${\tfrac {n}{k+1}}$ fallos de página esperados, sobre $n$ solicitudes. En cambio, un algoritmo fuera de línea puede dividir la secuencia de solicitudes en fases dentro de las cuales solo $k$ Las páginas se utilizan, incurriendo solo una falla al comienzo de una fase para reemplazar la página que no se utiliza dentro de la fase. Como ejemplo del problema del recolector de cupones , las solicitudes esperadas por fase son $(k+1)H_{k}$ , dónde $H_{k}=1+{\tfrac {1}{2}}+\cdots +{\tfrac {1}{k}}$ es el $k$ número armónico . Por teoría de renovación , el algoritmo fuera de línea incurre en ${\tfrac {n}{(k+1)H_{k}}}+o(n)$ fallos de página con alta probabilidad , por lo que la razón de competitividad de cualquier algoritmo determinista frente a esta distribución de entrada es al menos $H_{k}$ . Según el principio de Yao, $H_{k}$ También limita inferiormente la razón de competitividad de cualquier algoritmo de reemplazo de página aleatorio frente a una secuencia de solicitudes elegida por un adversario desprevenido como el peor caso para el algoritmo, pero sin conocimiento de las elecciones aleatorias del algoritmo. ^{[ 16 ]}

Para problemas en línea de una clase general relacionada con el problema del alquiler de esquís , Seiden ha propuesto un método de libro de recetas para derivar distribuciones de entrada óptimamente difíciles, basado en ciertos parámetros del problema. ^{[ 17 ]}

Relación con la teoría de juegos y la programación lineal.

El principio de Yao puede interpretarse en términos de teoría de juegos , mediante 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 del algoritmo seleccionado sobre la entrada seleccionada. Cualquier algoritmo aleatorio $R$ puede interpretarse como una elección aleatoria entre algoritmos deterministas y, por lo tanto, como una estrategia mixta para Alice. De manera similar, un algoritmo no aleatorio puede considerarse una estrategia pura para Alice. En cualquier juego de suma cero para dos jugadores, si un jugador elige una estrategia mixta, entonces el otro jugador tiene una estrategia pura óptima contra ella. Según el teorema minimax de John von Neumann , existe un valor de juego $c$ y estrategias mixtas para cada jugador, de manera que los jugadores puedan garantizar el valor esperado. $c$ o mejor jugando esas estrategias, y de tal manera que la estrategia pura óptima contra cualquiera de las estrategias mixtas produzca exactamente el valor esperado. $c$ Por lo tanto, la estrategia mixta minimax para Alice, contrapuesta a la mejor estrategia pura opuesta para Bob, produce el mismo valor esperado del juego. $c$ como la estrategia mixta minimax para Bob, en contraposición a la mejor estrategia pura opuesta para Alice. Esta igualdad de valores esperados del juego, para el juego descrito anteriormente, es el principio de Yao en su forma de igualdad. ^{[ 5 ]} El artículo de Yao de 1977, que formuló originalmente el principio de Yao, lo demostró de esta manera. ^{[ 2 ]}

La estrategia mixta óptima para Alice (un algoritmo aleatorio) y la estrategia mixta óptima para Bob (una distribución de entrada rígida) pueden calcularse mediante un programa lineal cuyas variables son las probabilidades de un jugador, con una restricción en el valor del juego para cada elección del otro jugador. Los dos programas lineales obtenidos de esta manera para cada jugador son programas lineales duales , cuya igualdad es una instancia de la dualidad de la programación lineal. ^{[ 3 ]} Sin embargo, aunque los programas lineales pueden resolverse en tiempo polinomial , el número de variables y restricciones en estos programas lineales (número de posibles algoritmos y entradas) suele ser demasiado grande para enumerarlo explícitamente. Por lo tanto, formular y resolver estos programas para encontrar estas estrategias óptimas suele ser poco práctico. ^{[ 13 ]}^{[ 14 ]}

Extensiones

For Monte Carlo algorithms, algorithms that use a fixed amount of computational resources but that may produce an erroneous result, a form of Yao's principle applies to the probability of an error, the error rate of an algorithm. Choosing the hardest possible input distribution, and the algorithm that achieves the lowest error rate against that distribution, gives the same error rate as choosing an optimal algorithm and its worst case input distribution. However, the hard input distributions found in this way are not robust to changes in the parameters used when applying this principle. If an input distribution requires high complexity to achieve a certain error rate, it may nevertheless have unexpectedly low complexity for a different error rate. Ben-David and Blais show that, for Boolean functions under many natural measures of computational complexity, there exists an input distribution that is simultaneously hard for all error rates.^[18]

Variants of Yao's principle have also been considered for quantum computing. In place of randomized algorithms, one may consider quantum algorithms that have a good probability of computing the correct value for every input (probability at least ${\tfrac {2}{3}}$ ); this condition together with polynomial time defines the complexity class BQP. It does not make sense to ask for deterministic quantum algorithms, but instead one may consider algorithms that, for a given input distribution, have probability 1 of computing a correct answer, either in a weak sense that the inputs for which this is true have probability $\geq {\tfrac {2}{3}}$ , or in a strong sense in which, in addition, the algorithm must have probability 0 or 1 of generating any particular answer on the remaining inputs. For any Boolean function, the minimum complexity of a quantum algorithm that is correct with probability $\geq {\tfrac {2}{3}}$ against its worst-case input is less than or equal to the minimum complexity that can be attained, for a hard input distribution, by the best weak or strong quantum algorithm against that distribution. The weak form of this inequality is within a constant factor of being an equality, but the strong form is not.^[19]

References

1 2 3 4Arora, Sanjeev; Barak, Boaz (2009), "Note 12.8: Yao's Min-Max Lemma", Computational Complexity: A Modern Approach, Cambridge University Press, p. 265, ISBN 9780511530753
1 2 3 4 5 6 Yao, Andrew (1977), "Cálculos probabilísticos: Hacia una medida unificada de complejidad", Actas del 18.º Simposio IEEE sobre Fundamentos de la Informática (FOCS) , págs. 222–227 , doi : 10.1109/SFCS.1977.24
1 2 Laraki, Rida ; Renault, Jérôme; Sorin, Sylvain (2019), "2.3 El teorema minmax", Fundamentos matemáticos de la teoría de juegos , Universitext, Springer, pp. 16–18 , doi : 10.1007/978-3-030-26646-2 , ISBN 978-3-030-26646-2
↑ Bohnenblust, HF; Karlin, S.; Shapley , LS (1950), "Soluciones de juegos discretos para dos personas", en Kuhn, Harold W .; Tucker, Albert William (eds.), Contribuciones a la teoría de juegos , Annals of Mathematics Studies, vol. 24, Princeton University Press, pp. 51–72 , doi : 10.1515/9781400881727-006 , ISBN 978-1-4008-8172-7, MR 0039218 {{citation}}: CS1 maint: errores de ISBN ignorados ( enlace )
1 2 3 Borodin, Allan ; El-Yaniv, Ran (2005), "8.3 Principio de Yao: Una técnica para obtener límites inferiores" , Online Computation and Competitive Analysis , Cambridge University Press, pp. 115–120 , ISBN 9780521619462
1 2 3 Wigderson, Avi (2019), Matemáticas y computación: una teoría que revoluciona la tecnología y la ciencia , Princeton University Press, pág. 210, ISBN 9780691189130
↑ Moore, Cristopher ; Mertens, Stephan (2011), "Teorema 10.1 (Principio de Yao)", La naturaleza de la computación , Oxford University Press, pág. 471, ISBN 9780199233212
1 2 Motwani, Rajeev ; Raghavan, Prabhakar (2010), "Capítulo 12: Algoritmos aleatorios", en Atallah, Mikhail J.; Blanton, Marina (eds.), Algoritmos y teoría de la computación: Manual de conceptos y técnicas generales (2.ª ed.), CRC Press, pp. 12-1 – 12-24 ; véase en particular la Sección 12.5: El principio minimax y los límites inferiores, págs. 12-8 – 12-10
↑ Cunto, Walter; Munro, J. Ian (1989), "Selección de casos promedio", Journal of the ACM , 36 (2): 270– 279, doi : 10.1145/62044.62047 , MR 1072421 , S2CID 10947879
↑ Chan, Timothy M. (2010), "Límites inferiores espacio-temporales basados en comparaciones para la selección", ACM Transactions on Algorithms , 6 (2): A26:1–A26:16, doi : 10.1145/1721837.1721842 , MR 2675693 , S2CID 11742607
↑ Knuth, Donald E. (1998), "Sección 5.3.3: Selección por comparación mínima", El arte de la programación informática, Volumen 3: Ordenación y búsqueda (2.ª ed.), Addison-Wesley, págs. 207–219 , ISBN 0-201-89685-0
↑ Chakrabarti, Amit; Khot, Subhash (2007), "Límites inferiores mejorados para la complejidad aleatoria de las propiedades de los grafos", Random Structures & Algorithms , 30 (3): 427–440 , doi : 10.1002/rsa.20164 , MR 2309625 , S2CID 8384071
1 2 3 4 Wegener, Ingo (2005), "9.2 Principio minimax de Yao", Teoría de la complejidad: Explorando los límites de los algoritmos eficientes , Springer-Verlag, pp. 118–120 , doi : 10.1007/3-540-27477-4 , ISBN 978-3-540-21045-0, MR 2146155
1 2 Fortnow, Lance (16 de octubre de 2006), "Teoremas favoritos: Principio de Yao" , Computación Computacional
↑ Viola, Emanuele (2015), "La complejidad comunicacional de la suma", Combinatorica , 35 (6): 703–747 , doi : 10.1007/s00493-014-3078-3 , MR 3439794
^ Borodin y El-Yaniv (2005) , págs. 120-122, 8.4 Paginación revisada.
↑ Seiden, Steven S. (2000), "Un juego de adivinanzas y algoritmos aleatorios en línea", en Yao, F. Frances ; Luks, Eugene M. (eds.), Actas del Trigésimo Segundo Simposio Anual de la ACM sobre Teoría de la Computación, 21-23 de mayo de 2000, Portland, OR, EE. UU ., pp. 592-601 , doi : 10.1145/335305.335385 , ISBN 1-58113-184-4
↑ Ben-David, Shalev; Blais, Eric (2023), "Un nuevo teorema minimax para algoritmos aleatorios", Journal of the ACM , 70 (6) 38, arXiv : 2002.10802 , doi : 10.1145/3626514 , MR 4679504
↑ de Graaf, Mart; de Wolf, Ronald (2002), "Sobre las versiones cuánticas del principio de Yao", en Alt, Helmut; Ferreira, Afonso (eds.), STACS 2002, 19.º Simposio Anual sobre Aspectos Teóricos de la Informática, Antibes – Juan les Pins, Francia, 14-16 de marzo de 2002, Actas , Lecture Notes in Computer Science, vol. 2285, Springer, pp. 347-358 , arXiv : quant-ph/0109070 , doi : 10.1007/3-540-45841-7_28 , ISBN 978-3-540-43283-8

[arobar-1] 1 2 3 4Arora, Sanjeev; Barak, Boaz (2009), "Note 12.8: Yao's Min-Max Lemma", Computational Complexity: A Modern Approach, Cambridge University Press, p. 265, ISBN 9780511530753

[yao-2] 1 2 3 4 5 6 Yao, Andrew (1977), "Cálculos probabilísticos: Hacia una medida unificada de complejidad", Actas del 18.º Simposio IEEE sobre Fundamentos de la Informática (FOCS) , págs. 222–227 , doi : 10.1109/SFCS.1977.24

[lareso-3] 1 2 Laraki, Rida ; Renault, Jérôme; Sorin, Sylvain (2019), "2.3 El teorema minmax", Fundamentos matemáticos de la teoría de juegos , Universitext, Springer, pp. 16–18 , doi : 10.1007/978-3-030-26646-2 , ISBN 978-3-030-26646-2

[bokash-4] Bohnenblust, HF; Karlin, S.; Shapley , LS (1950), "Soluciones de juegos discretos para dos personas", en Kuhn, Harold W .; Tucker, Albert William (eds.), Contribuciones a la teoría de juegos , Annals of Mathematics Studies, vol. 24, Princeton University Press, pp. 51–72 , doi : 10.1515/9781400881727-006 , ISBN 978-1-4008-8172-7, MR 0039218 {{citation}}: CS1 maint: errores de ISBN ignorados ( enlace )

[borel-5] 1 2 3 Borodin, Allan ; El-Yaniv, Ran (2005), "8.3 Principio de Yao: Una técnica para obtener límites inferiores" , Online Computation and Competitive Analysis , Cambridge University Press, pp. 115–120 , ISBN 9780521619462

[wigderson-6] 1 2 3 Wigderson, Avi (2019), Matemáticas y computación: una teoría que revoluciona la tecnología y la ciencia , Princeton University Press, pág. 210, ISBN 9780691189130

[nature-7] Moore, Cristopher ; Mertens, Stephan (2011), "Teorema 10.1 (Principio de Yao)", La naturaleza de la computación , Oxford University Press, pág. 471, ISBN 9780199233212

[motrag-8] 1 2 Motwani, Rajeev ; Raghavan, Prabhakar (2010), "Capítulo 12: Algoritmos aleatorios", en Atallah, Mikhail J.; Blanton, Marina (eds.), Algoritmos y teoría de la computación: Manual de conceptos y técnicas generales (2.ª ed.), CRC Press, pp. 12-1 – 12-24 ; véase en particular la Sección 12.5: El principio minimax y los límites inferiores, págs. 12-8 – 12-10

[cunmun-9] Cunto, Walter; Munro, J. Ian (1989), "Selección de casos promedio", Journal of the ACM , 36 (2): 270– 279, doi : 10.1145/62044.62047 , MR 1072421 , S2CID 10947879

[chan-10] Chan, Timothy M. (2010), "Límites inferiores espacio-temporales basados en comparaciones para la selección", ACM Transactions on Algorithms , 6 (2): A26:1–A26:16, doi : 10.1145/1721837.1721842 , MR 2675693 , S2CID 11742607

[knuth-11] Knuth, Donald E. (1998), "Sección 5.3.3: Selección por comparación mínima", El arte de la programación informática, Volumen 3: Ordenación y búsqueda (2.ª ed.), Addison-Wesley, págs. 207–219 , ISBN 0-201-89685-0

[chakho-12] Chakrabarti, Amit; Khot, Subhash (2007), "Límites inferiores mejorados para la complejidad aleatoria de las propiedades de los grafos", Random Structures & Algorithms , 30 (3): 427–440 , doi : 10.1002/rsa.20164 , MR 2309625 , S2CID 8384071

[wegener-13] 1 2 3 4 Wegener, Ingo (2005), "9.2 Principio minimax de Yao", Teoría de la complejidad: Explorando los límites de los algoritmos eficientes , Springer-Verlag, pp. 118–120 , doi : 10.1007/3-540-27477-4 , ISBN 978-3-540-21045-0, MR 2146155

[fortnow-14] 1 2 Fortnow, Lance (16 de octubre de 2006), "Teoremas favoritos: Principio de Yao" , Computación Computacional

[viola-15] Viola, Emanuele (2015), "La complejidad comunicacional de la suma", Combinatorica , 35 (6): 703–747 , doi : 10.1007/s00493-014-3078-3 , MR 3439794

[FOOTNOTEBorodinEl-Yaniv2005120–1228.4_Paging_revisited-16] Borodin y El-Yaniv (2005) , págs. 120-122, 8.4 Paginación revisada.

[seiden-17] Seiden, Steven S. (2000), "Un juego de adivinanzas y algoritmos aleatorios en línea", en Yao, F. Frances ; Luks, Eugene M. (eds.), Actas del Trigésimo Segundo Simposio Anual de la ACM sobre Teoría de la Computación, 21-23 de mayo de 2000, Portland, OR, EE. UU ., pp. 592-601 , doi : 10.1145/335305.335385 , ISBN 1-58113-184-4

[benbla-18] Ben-David, Shalev; Blais, Eric (2023), "Un nuevo teorema minimax para algoritmos aleatorios", Journal of the ACM , 70 (6) 38, arXiv : 2002.10802 , doi : 10.1145/3626514 , MR 4679504

[grawol-19] Graaf, Mart; de Wolf, Ronald (2002), "Sobre las versiones cuánticas del principio de Yao", en Alt, Helmut; Ferreira, Afonso (eds.), STACS 2002, 19.º Simposio Anual sobre Aspectos Teóricos de la Informática, Antibes – Juan les Pins, Francia, 14-16 de marzo de 2002, Actas , Lecture Notes in Computer Science, vol. 2285, Springer, pp. 347-358 , arXiv : quant-ph/0109070 , doi : 10.1007/3-540-45841-7_28 , ISBN 978-3-540-43283-8

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[18]

[19]