Zasada Yao

W teorii złożoności obliczeniowej zasada Yao (zwana także zasadą minimaksu Yao lub lematem Yao ) jest sposobem na udowodnienie dolnych granic wydajności losowych algorytmów w najgorszym przypadku , porównując je z algorytmami deterministycznymi (nielosowymi). Stwierdza, że ​​dla dowolnego losowego algorytmu istnieje rozkład prawdopodobieństwa danych wejściowych algorytmu, tak że oczekiwany koszt losowego algorytmu na jego danych wejściowych w najgorszym przypadku jest co najmniej tak duży, jak koszt najlepszego algorytmu deterministycznego na losowe dane wejściowe z tej dystrybucji. Zatem, aby ustalić dolną granicę wydajności losowych algorytmów, wystarczy znaleźć odpowiedni rozkład trudnych danych wejściowych i udowodnić, że żaden algorytm deterministyczny nie może dobrze działać w stosunku do tego rozkładu. Zasada ta nosi imię Andrew Yao , który pierwszy to zaproponował.

Zasada Yao może być interpretowana w kategoriach teorii gier , poprzez dwuosobową grę o sumie zerowej , w której jeden gracz, Alicja , wybiera algorytm deterministyczny, drugi gracz, Bob, wybiera dane wejściowe, a wypłatą jest koszt wybranego algorytm na wybranym wejściu. Każdy losowy algorytm R może być interpretowany jako losowy wybór spośród algorytmów deterministycznych, a więc jako strategia mieszana dla Alicji. Podobnie, nielosowy algorytm może być traktowany jako czysta strategia dla Alicji. Przez von Neumanna twierdzenie o minimaksie , Bob ma losową strategię, która sprawdza się co najmniej tak samo dobrze w przypadku R , jak w przypadku najlepszej czystej strategii, którą mogła wybrać Alicja. Dane wejściowe najgorszego przypadku w porównaniu ze strategią Alicji kosztowały co najmniej tyle samo, co losowo wybrane dane wejściowe Boba w połączeniu ze strategią Alicji, co z kolei kosztowało co najmniej tyle samo, co losowo wybrane dane wejściowe Boba w połączeniu z jakąkolwiek czystą strategią.

Oświadczenie

Poniższe sformułowanie określa zasadę losowych algorytmów Las Vegas , tj. rozkładów po algorytmach deterministycznych, które są poprawne na każdym wejściu, ale mają różne koszty. Łatwo jest dostosować tę zasadę do algorytmów Monte Carlo , tj. rozkładów po algorytmach deterministycznych, które mają ograniczone koszty, ale mogą być niepoprawne na niektórych danych wejściowych.

Rozważ problem na wejściach $,$ niech będzie $.$ które poprawnie rozwiązują problem Dla dowolnego algorytmu i wejścia $}}}$${\ Displaystyle a \ in {\ mathcal$$displaystyle c(a,x)\geq 0}$ , niech ${$ będzie kosztem algorytmu ${\ displaystyle a}$ uruchamiane na wejściu ${\ displaystyle x}$ .

Niech $będzie$ rozkładem prawdopodobieństwa algorytmów $oznacza$ niech $displaystyle$ algorytm wybrany zgodnie z $p}$ . Niech $będzie rozkładem prawdopodobieństwa$$}$ wejściach i niech oznacza losowe dane wejściowe wybrane zgodnie z q $displaystyle$$.$ Następnie,

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

$wejściowych$ , że oczekiwany koszt losowego algorytmu w najgorszym przypadku jest co najmniej oczekiwanym kosztem najlepszego algorytmu deterministycznego względem rozkładu danych .

Dowód

Niech do $\ Displaystyle C = {\ underset {x \ in {\ mathcal {X}}} {\ max}} \ \ mathbf {E} [c ( A, x)]}$ i re $Displaystyle D = {\ underset {a \ in {\ mathcal {A}}} {\ min}} \ \ mathbf {E} [c(a,X)]}$ . Mamy

${\ Displaystyle {\ rozpocząć {wyrównane} C & = \ suma _ {x} q_ {x} C \\ & \ geq \ suma _ {x} q_ {x} \ mathbf {E} [c (A, x)] \\&=\suma _{x}q_{x}\suma _{a}p_{a}c(a,x)\\&=\suma _{a}p_{a}\suma _{x} q_{x}c(a,x)\\&=\suma _{a}p_{a}\mathbf {E} [c(a,X)]\\&\geq \suma _{a}p_{ a}D=D.\end{wyrównane}}}$

Jak wspomniano powyżej, twierdzenie to można również postrzegać jako bardzo szczególny przypadek twierdzenia Minimax .

Zobacz też

• Losowe algorytmy jako gry o sumie zerowej

•   Borodin, Allan ; El-Yaniv, Ran (2005), „8.3 Zasada Yao: technika uzyskiwania dolnych granic” , Online Computation and Competitive Analysis , Cambridge University Press, s. 115–120, ISBN 9780521619462
• Yao, Andrew (1977), „Obliczenia probabilistyczne: w kierunku ujednoliconej miary złożoności”, Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (FOCS) , s. 222–227, doi : 10.1109 / SFCS.1977.24

Linki zewnętrzne

• Fortnow, Lance (16 października 2006), „Ulubione twierdzenia: zasada Yao” , Złożoność obliczeniowa