Princípio de Yao - Yao's principle

Na teoria da complexidade computacional , o princípio de Yao (também chamado de princípio minimax de Yao ou lema de Yao ) afirma que o custo esperado de um algoritmo aleatório na entrada de pior caso não é melhor do que o custo esperado para uma distribuição de probabilidade de pior caso nas entradas de o algoritmo determinístico com melhor desempenho nessa distribuição. Assim, para estabelecer um limite inferior no desempenho de algoritmos aleatórios, é suficiente encontrar uma distribuição apropriada de entradas difíceis e provar que nenhum algoritmo determinístico pode funcionar bem contra essa distribuição. Este princípio tem o nome de Andrew Yao , que o propôs pela primeira vez.

O princípio de Yao pode ser interpretado em termos da teoria do jogo , por meio de um jogo de soma zero para dois jogadores em que um jogador, Alice , seleciona um algoritmo determinístico, o outro jogador, Bob, seleciona uma entrada, e a recompensa é o custo da algoritmo na entrada selecionada. Qualquer algoritmo R aleatório pode ser interpretado como uma escolha aleatória entre algoritmos determinísticos e, portanto, como uma estratégia para Alice. Pelo teorema minimax de von Neumann , Bob tem uma estratégia aleatória que funciona pelo menos tão bem contra R quanto contra a melhor estratégia pura que Alice poderia escolher; ou seja, a estratégia de Bob define uma distribuição nas entradas de forma que o custo esperado de R nessa distribuição (e, portanto, também o custo esperado de R no pior caso ) não seja melhor do que o custo esperado de qualquer algoritmo determinístico único em relação à mesma distribuição.

Demonstração

A formulação abaixo estabelece o princípio para algoritmos randomizados de Las Vegas , ou seja, distribuições sobre algoritmos determinísticos que estão corretos em todas as entradas, mas têm custos variáveis. É simples adaptar o princípio aos algoritmos de Monte Carlo , ou seja, distribuições sobre algoritmos determinísticos que têm custos limitados, mas podem estar incorretos em algumas entradas.

Considere um problema sobre as entradas e seja o conjunto de todos os algoritmos determinísticos possíveis que resolvem o problema corretamente. Para qualquer algoritmo e entrada , deixe ser o custo do algoritmo executado na 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}$

Let Ser uma distribuição de probabilidade sobre os algoritmos , e deixe denotar um algoritmo aleatório escolhido de acordo com . Let Ser uma distribuição de probabilidade sobre as entradas , e vamos denotar uma entrada aleatória escolhida de acordo com . Então, ${\ 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)].}$

Ou seja, o custo esperado do pior caso do algoritmo aleatório é pelo menos o custo esperado do melhor algoritmo determinístico em relação à distribuição de entrada . ${\ displaystyle q}$

Prova

Deixe e . Nós temos ${\ 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 {alinhados} 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 {alinhado}}}$

Como mencionado acima, este teorema também pode ser visto como um caso muito especial do teorema Minimax .

Referências

• Borodin, Allan ; El-Yaniv, Ran (2005), "8.3 Yao's Princípio: Uma técnica para obter limites inferiores" , Online Computation and Competitive Analysis , Cambridge University Press, pp. 115-120, ISBN 9780521619462
• Yao, Andrew (1977), "Probabilistic computations: Toward a unified measure of complex", Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (FOCS) , pp. 222-227, doi : 10.1109 / SFCS.1977.24

links externos

• Fortnow, Lance (16 de outubro de 2006), "Teoremas favoritos: princípio de Yao" , Complexidade computacional