Hispanopedia Wiki
Articulo de referencia

El principio de Yao

\n"}"> 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 al...

Hispanopedia WikiContenido en espanolLectura gratuita
Este es un buen artículo. Haz clic aquí para obtener más información.

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 de un algoritmo sobre una entrada , como su tiempo de ejecución, para la 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 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 , que puede hacerse finito de la misma manera. Entonces, cada distribución de probabilidad sobre corresponde a un algoritmo aleatorio que primero hace una elección aleatoria de según 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 de todas las distribuciones de probabilidad sobre . Finalmente, la formulación del principio de Yao involucra la clase de todas las distribuciones de probabilidad sobre entradas en , denotada como . Entonces, el principio de Yao establece que: [ 1 ]do(A,incógnita){\displaystyle c(A,x)}A{\displaystyle A}incógnita{\displaystyle x}A{\displaystyle {\mathcal {A}}}incógnita{\displaystyle {\mathcal {X}}}A{\displaystyle {\mathcal {A}}}A{\displaystyle {\mathcal {A}}}R{\displaystyle {\mathcal {R}}}A{\displaystyle {\mathcal {A}}}incógnita{\displaystyle {\mathcal {X}}}D{\displaystyle {\mathcal {D}}}

máximoD∈DminA∈Amiincógnita∼D[do(A,incógnita)]=minR∈Rmáximoincógnita∈incógnitami[do(R,incógnita)].{\displaystyle \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í, es la notación para el valor esperado, y significa que es una variable aleatoria distribuida según . El lado izquierdo de la fórmula da el rendimiento óptimo que puede obtener un algoritmo determinista en una entrada aleatoria (su complejidad en el caso promedio ), para una distribución de probabilidad en las entradas que es lo más difícil posible y siendo el algoritmo que mejor se desempeña contra . El lado derecho da el rendimiento óptimo que puede obtener un algoritmo aleatorio en una entrada determinista (su complejidad esperada), cuando tiene el mejor rendimiento en sus peores entradas de caso, y cuando es una peor entrada de caso para . [ 1 ] La finitud de y permite que y se interpreten como símplices de vectores de probabilidad , [ 3 ] cuya compacidad implica que existen los mínimos y máximos en estas fórmulas. [ 4 ]mi{\displaystyle \mathbb {E} }incógnita∼D{\displaystyle x\sim D}incógnita{\displaystyle x}D{\displaystyle D}A{\displaystyle A}incógnita{\displaystyle x}D{\displaystyle D}A{\displaystyle A}D{\displaystyle D}R{\displaystyle R}incógnita{\displaystyle x}R{\displaystyle R}incógnita{\displaystyle x}R{\displaystyle R}A{\displaystyle {\mathcal {A}}}incógnita{\displaystyle {\mathcal {X}}}D{\displaystyle {\mathcal {D}}}R{\displaystyle {\mathcal {R}}}

Otra versión del principio de Yao lo debilita 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 que se utilice cuando se ha demostrado que una distribución de entrada específica es difícil para los algoritmos deterministas, convirtiéndola en una cota inferior en el costo de todos los algoritmos aleatorios. En esta versión, para cada distribución de entrada ,D∈D{\displaystyle D\in {\mathcal {D}}} y para cada algoritmo aleatorio en , [ 1 ]R{\displaystyle R}R{\displaystyle {\mathcal {R}}} Es decir, el mejor rendimiento determinista posible contra la distribución es una cota inferior para el rendimiento de cada algoritmo aleatorio contra su entrada de peor caso. Esta versión del principio de Yao se puede demostrar a través de la cadena de desigualdades cada una de las cuales se puede demostrar utilizando solo la linealidad de la esperanza y el principio de que para todas las distribuciones. Al evitar la maximización y la minimización sobre y , esta versión del principio de Yao se puede aplicar en algunos casos donde o no son finitos. [ 5 ] Si bien 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 usarlo 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 ]minA∈Amiincógnita∼D[do(A,incógnita)]≤máximoincógnita∈incógnitami[do(R,incógnita)].{\displaystyle \min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]\leq \max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)].}D{\displaystyle D}R{\displaystyle R}minA∈Amiincógnita∼D[do(A,incógnita)]≤miincógnita∼D[do(R,incógnita)]≤máximoincógnita∈incógnitami[do(R,incógnita)],{\displaystyle \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)],}min≤mi≤máximo{\displaystyle \min \leq \mathbb {E} \leq \max }D{\displaystyle {\mathcal {D}}}R{\displaystyle {\mathcal {R}}}incógnita{\displaystyle {\mathcal {X}}}A{\displaystyle {\mathcal {A}}}

Aplicaciones y ejemplos

complejidad temporal

Cuando el costo 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 ]do{\displaystyle c}

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 indicador 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 forma, 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 sobre elementos distintos para las que 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 comparaciones realizadas por algoritmos deterministas, para permutaciones aleatorias, al análisis del peor caso de algoritmos de comparación aleatorios. [ 2 ]norte{\displaystyle n}

Un ejemplo dado por Yao es el análisis de algoritmos para encontrar el enésimo mayor de un conjunto dado de 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 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 de las comparaciones de este límite. [ 11 ]k{\displaystyle k}norte{\displaystyle n}norte+min(k,norte−k)−O(1){\displaystyle n+\min(k,nk)-O(1)}O(norteregistro⁡norte){\displaystyle O({\sqrt {n\log n}})}

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 con vértices y un número limitado 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 , porque el grafo de utilidad de 9 aristas no es planar. Más precisamente, Yao afirma que para estas propiedades, se necesitan al menos pruebas, para cada , para que un algoritmo aleatorio tenga una probabilidad como máximo 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 ]norte{\displaystyle n}s{\displaystyle s}s=9{\displaystyle s=9}(12−pag)1s(norte2){\displaystyle \left({\tfrac {1}{2}}-p\right){\tfrac {1}{s}}{\tbinom {n}{2}}}ε>0{\displaystyle \varepsilon >0}pag{\displaystyle p}

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 cadenas binarias de bits que comprueban si la entrada es igual a una cadena fija pero desconocida, el número óptimo esperado de llamadas a la función necesarias para encontrar la cadena desconocida es . Esto se puede lograr mediante una función que prueba cadenas en un orden aleatorio, y se demostró que es óptimo utilizando el principio de Yao en una distribución de entrada que elige una función aleatoria uniforme de esta clase. [ 13 ]norte{\displaystyle n}2norte−1+12{\displaystyle 2^{n-1}+{\tfrac {1}{2}}}
  • Una función unimodal de cadenas binarias de bits a números reales se define por la siguiente propiedad: Para cada cadena de entrada , o bien es el valor máximo único de , o bien puede cambiarse en un solo bit a una cadena 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 consultas, alguna función de esta clase hará que el algoritmo tenga una probabilidad exponencialmente pequeña de encontrar el máximo. [ 13 ]F{\displaystyle f}norte{\displaystyle n}incógnita{\displaystyle x}F(incógnita){\displaystyle f(x)}F{\displaystyle f}incógnita{\displaystyle x}y{\displaystyle y}2o(norte){\displaystyle 2^{o(n)}}

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 entre dos partes, cada una con valores de entrada de bits, para determinar cuál es mayor. Para protocolos de comunicación deterministas, no es posible una comunicación mejor que bits, que se logra fácilmente enviando una parte 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 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 ]norte{\displaystyle n}norte{\displaystyle n}O(registro⁡norte){\displaystyle O(\log n)}

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 algoritmos de reemplazo de páginas , que responden a solicitudes de páginas de memoria de computadora utilizando una caché de páginas, para un parámetro dado . 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 páginas. Cualquier algoritmo en línea determinista tiene fallas de página esperadas, sobre solicitudes. En cambio, un algoritmo fuera de línea puede dividir la secuencia de solicitudes en fases dentro de las cuales solo se usan páginas, incurriendo solo una falla al comienzo de una fase para reemplazar la página que no se usa dentro de la fase. Como instancia del problema del recolector de cupones , las solicitudes esperadas por fase son , donde es el -ésimo número armónico . Por la teoría de renovación , el algoritmo fuera de línea incurre en fallas de página con alta probabilidad , por lo que la razón competitiva de cualquier algoritmo determinista contra esta distribución de entrada es al menos . Según el principio de Yao, también se establecen límites inferiores para la razón de competitividad de cualquier algoritmo de reemplazo de página aleatorio frente a una secuencia de solicitudes elegida por un adversario ajeno a la situación como el peor caso para el algoritmo, pero sin conocimiento de las elecciones aleatorias del algoritmo. [ 16 ]k{\displaystyle k}k{\displaystyle k}k+1{\displaystyle k+1}nortek+1{\displaystyle {\tfrac {n}{k+1}}}norte{\displaystyle n}k{\displaystyle k}(k+1)Hk{\displaystyle (k+1)H_{k}}Hk=1+12+⋯+1k{\displaystyle H_{k}=1+{\tfrac {1}{2}}+\cdots +{\tfrac {1}{k}}}k{\displaystyle k}n(k+1)Hk+o(n){\displaystyle {\tfrac {n}{(k+1)H_{k}}}+o(n)}Hk{\displaystyle H_{k}}Hk{\displaystyle H_{k}}

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 , 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 del algoritmo seleccionado sobre la entrada seleccionada. Cualquier algoritmo aleatorio 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 pensarse como 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. Por el teorema minimax de John von Neumann , existe un valor de juego y estrategias mixtas para cada jugador, tales que los jugadores pueden garantizar un valor esperado o mejor al jugar esas estrategias, y tales que la estrategia pura óptima contra cualquiera de las estrategias mixtas produce un valor esperado exactamente . Así, la estrategia mixta minimax para Alice, frente a la mejor estrategia pura opuesta para Bob, produce el mismo valor esperado del juego que la estrategia mixta minimax para Bob, frente 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 ]R{\displaystyle R}c{\displaystyle c}c{\displaystyle c}c{\displaystyle c}c{\displaystyle c}

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

Para los algoritmos de Monte Carlo , algoritmos que utilizan una cantidad fija de recursos computacionales pero que pueden producir un resultado erróneo, se aplica una forma del principio de Yao a la probabilidad de error, la tasa de error de un algoritmo. Elegir la distribución de entrada más difícil posible y el algoritmo que logra la menor tasa de error frente a esa distribución da como resultado la misma tasa de error que elegir un algoritmo óptimo y su distribución de entrada en el peor de los casos. Sin embargo, las distribuciones de entrada difíciles encontradas de esta manera no son robustas a los cambios en los parámetros utilizados al aplicar este principio. Si una distribución de entrada requiere una alta complejidad para lograr una determinada tasa de error, puede tener, no obstante, una complejidad inesperadamente baja para una tasa de error diferente. Ben-David y Blais demuestran que, para funciones booleanas bajo muchas medidas naturales de complejidad computacional, existe una distribución de entrada que es simultáneamente difícil para todas las tasas de error. [ 18 ]

También se han considerado variantes del principio de Yao para la computación cuántica . En lugar de algoritmos aleatorios, se pueden considerar algoritmos cuánticos que tengan una buena probabilidad de calcular el valor correcto para cada entrada (probabilidad al menos ); esta condición junto con el tiempo polinomial define la clase de complejidad BQP . No tiene sentido pedir algoritmos cuánticos deterministas, sino que se pueden considerar algoritmos que, para una distribución de entrada dada, tengan una probabilidad 1 de calcular una respuesta correcta, ya sea en un sentido débil en el que las entradas para las que esto es cierto tienen probabilidad , o en un sentido fuerte en el que, además, el algoritmo debe tener una probabilidad 0 o 1 de generar cualquier respuesta particular en las entradas restantes. Para cualquier función booleana, la complejidad mínima de un algoritmo cuántico que es correcto con probabilidad frente a su peor caso de entrada es menor o igual que la complejidad mínima que puede alcanzarse, para una distribución de entrada difícil, por el mejor algoritmo cuántico débil o fuerte frente a esa distribución. La forma débil de esta desigualdad está dentro de un factor constante de ser una igualdad, pero la forma fuerte no lo es. [ 19 ]23{\displaystyle {\tfrac {2}{3}}}≥23{\displaystyle \geq {\tfrac {2}{3}}}≥23{\displaystyle \geq {\tfrac {2}{3}}}

Referencias

  1. 1 2 3 4 Arora, Sanjeev ; Barak, Boaz (2009), "Nota 12.8: Lema min-max de Yao", Complejidad computacional: un enfoque moderno , Cambridge University Press, pág. 265 , ISBN  9780511530753
  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 
  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
  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: ignored ISBN errors (link)
  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
  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
  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
  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 
  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  
  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  
  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
  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  
  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 
  14. 1 2 Fortnow, Lance (16 de octubre de 2006), "Teoremas favoritos: Principio de Yao" , Computación Computacional
  15. ↑ Viola, Emanuele (2015), "La complejidad comunicacional de la suma", Combinatorica , 35 (6): 703–747 , doi : 10.1007/s00493-014-3078-3 , MR 3439794 
  16. ^ Borodin y El-Yaniv (2005) , págs. 120-122, 8.4 Paginación revisada.
  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
  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 
  19. ↑ 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
Obtenido de " https://en.wikipedia.org/w/index.php?title=Yao%27s_principle&oldid=1343886918 "
Lecturas relacionadas
6 articulos
Teoría de la complejidad computacionalEn la informática teórica y las matemáticas, la teoría de la complejidad computacional se centra en la clasificación de los problemas computacional...{\displaystyle \lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}Algoritmo aleatorioUn algoritmo aleatorio es un algoritmo que emplea un grado de aleatoriedad como parte de su lógica o procedimiento. El algoritmo normalmente utiliz...Algoritmo deterministaAlgoritmo deterministaEn informática , un algoritmo determinista es un algoritmo que, dada una entrada particular, siempre producirá la misma salida, y la máquina subyac...{\displaystyle \Pr_{x\in_{R}D_{n}}\left[t_{A}(x)\geq t\right]\leq {\frac {p(n)}{t^{\epsilon }}}}Complejidad de caso promedioEn la teoría de la complejidad computacional , la complejidad del caso promedio de un algoritmo es la cantidad de algún recurso computacional (norm...Distribución de probabilidadEn teoría de probabilidad y estadística , una distribución de probabilidad es la función matemática que da las probabilidades de ocurrencia de posi...Análisis del peor escenarioEl análisis del peor escenario fue, desde 1978 hasta 1986, una doctrina bajo 40 U.SC § 1502.22 que exigía que una declaración de impacto ambiental ...