next up previous contents
Next: Eredményeink a bonyolultságelmélet köréből Up: Motiváció és irodalmi áttekintés Previous: Boole-hálózatok

Kommunikációs játékok

A kommunikációs játékok fogalmát Yao [52] vezette be 1979-ben. Ebben a modellben két játékos, Alíz és Bob szeretne kiszámolni egy $f:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}$ függvényt, úgy, hogy Alíz csak az $x\in\{0,1\}^n$, Bob csak az $y\in\{0,1\}^n$ változót ismeri. Mind Alíz, mind pedig Bob lokálisan ingyen számolhat, azonban minden egymás között küldött bitért 1 Ft-ot kell fizetniük. Egy protokoll költsége a költségek maximuma az $(x,y)\in\{0,1\}^n\times\{0,1\}^n$ párokra nézve, azaz más szóval, a legdrágábban kiszámolt f(x,y) érték költsége; egy f függvény $\kappa(f)$ kommunikációs bonyolultsága pedig a legjobb, őt kiszámoló protokoll költsége. (Bővebb bevezetés található a [39] survey-cikkben, vagy a [37] monográfiában.)

Az $f:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}$ függvény kommunikációs mátrixa egy $M_f\in\{0,1\}^{2^n\times2^n}$ mátrix, ahol a mátrix sorai az x, oszlopai pedig az y különböző értékeivel vannak indexelve; a mátrix x sorának és y oszlopának metszetében áll az f(x,y) érték. Mehlhorn és Schmidt [41] bizonyította be, hogy

\begin{displaymath}\kappa(f)\geq\log\hbox{\rm rank}(M_f).\eqno{(1)}\end{displaymath}

Nem nehéz belátni, hogy

\begin{displaymath}\kappa(f)\leq\hbox{\rm rank}(M_f), \end{displaymath}

azonban nincs példa arra, hogy ez utóbbi egyenlőtlenség éles lenne. Sőt, Lovász és Saks [40] sejti, hogy az is igaz, hogy létezik olyan c>0, hogy

\begin{displaymath}\kappa(f)\leq(\log\hbox{\rm rank}(M_f))^c.\end{displaymath}

A kétrésztvevős kommunikációs játékok egyik lehetséges általánosítását adta több játékosra Chandra, Furst és Lipton [13]. Ebben a modellben k játékos, $P_1, P_2, \ldots, P_k$ szeretne kiszámolni egy

\begin{displaymath}g:\{0,1\}^{kn}\to{\mathbf Z^+_0}\eqno{(2)}\end{displaymath}

függvényt, ahol is <I>Z+0 jelöli a nem-negatív egész számok halmazát, és még az is teljesül, hogy $g(A_1,A_2,\ldots,A_k)$ függvény $A_i\in\{0,1\}^n$ változóján kívül a Pi játékos az összes többi inputot ismeri, $i=1,2,\ldots,k$-ra. Egy protokoll költsége ismét a számítás során kommunikált bitek száma.

Babai, Nisan és Szegedy híres cikkében [6] mutatta meg, hogy az általánosított belső-szorzat függvény (GIP) k-résztvevős kommunikációs bonyolultága legalább

\begin{displaymath}\Omega\left({n\over4^k}\right).\eqno{(3)}\end{displaymath}

Hstad és Goldmann [33] mutatott érdekes kapcsolatot a fenti BNS alsó becslés felhasználhatóságára Boole-hálózatok méretének alsó becslésére. Tegyük fel, hogy az (2) g-függvényének k-résztvevős kommunikációs bonyolultsága t(n,k). Tegyük fel továbbá, hogy a g függvényt ki lehet számítani egy olyan, kettő mélységű és M méretű hálózattal, amely tetején egy szimmetrikus függvényt kiszámító kapu (pl. ÉS, VAGY, $\hbox{\rm MOD}_6$) van, és ez alatt, az input-változókkal összekötve pedig tetszőleges, de legfeljebb k-1 bemenetű kapuk helyezkednek el. Mivel a k-résztvevős játékban minden változót pontosan egy játékos nem ismer, ezért minden alsó kapuhoz van olyan játékos, aki ismeri minden bemenetét az illető kapunak, így a kapu értékét is; a játékosok így, $k\log M$ kommunikációval kiszámolhatják a g függvény értékét, másrészt viszont, a feltevésünkből, $k\log M\geq t(n,k)$. Így, ha például $t(n,k)\geq n^\varepsilon$, és k kicsi, akkor M, a hálózat mérete, exponenciális kell, hogy legyen n-ben.


next up previous contents
Next: Eredményeink a bonyolultságelmélet köréből Up: Motiváció és irodalmi áttekintés Previous: Boole-hálózatok
Vince Grolmusz
1999-11-08