Yaos princip

I beräkningskomplexitetsteori är Yaos princip (även kallad Yaos minimaxprincip eller Yaos lemma ) ett sätt att bevisa lägre gränser för slumpmässiga algoritmers värsta tänkbara prestanda , genom att jämföra dem med deterministiska (icke-slumpmässiga) algoritmer . Den anger att det för varje randomiserad algoritm finns en sannolikhetsfördelning på indata till algoritmen, så att den förväntade kostnaden för den randomiserade algoritmen på dess värsta tänkbara indata är minst lika stor som kostnaden för den bästa deterministiska algoritmen på en slumpmässig input från denna distribution. För att fastställa en nedre gräns för prestandan hos randomiserade algoritmer räcker det alltså att hitta en lämplig fördelning av svåra indata, och att bevisa att ingen deterministisk algoritm kan fungera bra mot den fördelningen. Denna princip är uppkallad efter Andrew Yao , som först föreslog den.

Yaos princip kan tolkas i spelteoretiska termer, via ett nollsummespel för två spelare där en spelare, Alice , väljer en deterministisk algoritm, den andra spelaren, Bob, väljer en ingång, och utdelningen är kostnaden för den valda algoritm på den valda ingången. Vilken randomiserad algoritm R som helst kan tolkas som ett randomiserat val bland deterministiska algoritmer, och därmed som en blandad strategi för Alice. På samma sätt kan en icke-slumpmässig algoritm ses som en ren strategi för Alice. Enligt von Neumanns minimaxteorem har Bob en randomiserad strategi som presterar minst lika bra mot R som den gör mot den bästa rena strategin som Alice kan ha valt. Den värsta insatsen mot Alices strategi har kostat minst lika stor som Bobs slumpmässigt valda input parad mot Alices strategi, vilket i sin tur har kostat minst lika stor som Bobs slumpmässigt valda input parat mot någon ren strategi.

Påstående

Formuleringen nedan anger principen för Las Vegas randomiserade algoritmer, dvs fördelningar över deterministiska algoritmer som är korrekta på varje ingång men har varierande kostnader. Det är enkelt att anpassa principen till Monte Carlo- algoritmer, det vill säga fördelningar över deterministiska algoritmer som har begränsade kostnader men som kan vara felaktiga på vissa indata.

Betrakta ett problem med ingångarna ${\mathcal {X}}$ och låt ${\mathcal {A}}$ vara uppsättningen av alla möjliga deterministiska algoritmer som korrekt löser problemet. För vilken algoritm som helst $a\in {\mathcal {A}}$ och inmatning $x\in {\mathcal {X}}$ , låt ${\ displaystyle c(a,x)\geq 0}$ vara kostnaden för algoritmen $a$ körning på ingång $x$ .

Låt $p$ vara en sannolikhetsfördelning över algoritmerna ${\displaystyle {\mathcal {A}}} ,$ och låt $A$ beteckna en slumpmässig algoritm vald enligt $p$ . Låt $q$ vara en sannolikhetsfördelning över ingångarna ${\mathcal {X}}$ , och låt $X$ beteckna en slumpmässig ingång vald enligt $q$ . Sedan,

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

Det vill säga den värsta förväntade kostnaden för den randomiserade algoritmen är åtminstone den förväntade kostnaden för den bästa deterministiska algoritmen mot ingångsfördelning $q$ .

Bevis

Låt $C={\underset {x\in {\mathcal {X}}}{\max }}\ \mathbf {E} [c( A,x)]$ och $D={\underset {a\in {\mathcal {A}}}{\min }}\ \mathbf {E} [c(a,X)]$ . Vi har

${\begin{aligned}C&=\sum _{x}q_{x}C\\&\geq \sum _{x}q_{x}\mathbf {E} [c(A,x)] \\&=\summa _{x}q_{x}\summa _{a}p_{a}c(a,x)\\&=\summa _{a}p_{a}\summa _{x} q_{x}c(a,x)\\&=\summa _{a}p_{a}\mathbf {E} [c(a,X)]\\&\geq \summa _{a}p_{ a}D=D.\end{aligned}}$

Som nämnts ovan kan denna sats också ses som ett mycket speciellt fall av Minimax-satsen .

Se även

• Randomiserade algoritmer som nollsummespel

•   Borodin, Allan ; El-Yaniv, Ran (2005), "8.3 Yaos princip: En teknik för att uppnå lägre gränser" , Online Computation and Competitive Analysis , Cambridge University Press, s. 115–120, ISBN 9780521619462
• Yao, Andrew (1977), "Probabilistic computations: Toward a unified measure of complexity", Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (FOCS) , s. 222–227, doi : 10.1109/SFCS.1977.24

externa länkar

• Fortnow, Lance (16 oktober 2006), "Favoritsatser: Yao-principen" , Computational Complexity