Matematika | Felsőoktatás » Róka Dániel - Többszereplős kommunikációs komplexitás

Tobbszerepl}os kommunikacios komplexitas SZAKDOLGOZAT Kesztette: Roka Daniel Temavezet}ok: Tardos Gabor Katona Gyula 1 Absztrakt: A Yao altal denialt ket szerepl}os kommunikacios modell lehet}oseget knal a szerepl}ok szama szerinti altalanostasra. Ennek rengeteg kulonboz}o modja lehet, melyek kozul tobbet is megprobalunk attekinteni. Egy ilyen lehet}oseg a linearis halozat, melyet P Tiwari vetett fel egy 1987-es cikkeben, majd erdemenyei 1996-97-ben lettek pontostva. A ,,homlokra ragasztott szam" modell az el}obbit}ol igen elter Ebben is ismert tobb eredmeny Mind also, mind fels}o becslesek akadnak szep szammal bizonyos fuggvenyek kommunikacios komplexitasara, melyek azonban nem teljesen kielegt}oek, hiszen minden eddig ismert also becsles a szerepl}ok szamanak novekedesevel exponencialisan csokken. E ket modell reszletes vizsgalatan kvul felvetunk egy uj kommunikacios modellt: a csillag

modellt, melyet a jelen szakdolgozat vizsgal el}oszor. Tartalom: 1. Tobbszerepl}os kommunikacios komplexitas 2. A linearis halozat 3. A ,,homlokra ragasztott szam" modell 4. A csillag modell 2 1. Tobbszerepl}os kommunikacios komplexitas A Yao fele ketszerepl}os kommunikacio A Yao fele kommunikacios modellben ket jatekos, A es B mindegyike rendelkezik egyegy sajat inputtal. A szamara x 2 X , B szamara pedig y 2 Y ismert, ahol X , illetve Y a jatekosok szamara lehetseges inputok halmazai. Egy f : X  Y ;! f0 1g fuggveny mellett szeretnek f (x y)-t kiszamtani, megpedig ugy, hogy a lehet}o legkevesebb bitet kelljen egymasnak elkuldeni. A jatekosok tetsz}oleges mennyiseg}u szamtast vegezhetnek, csak az egymasnak elkuldott informacioert kell ,,zetni". Egy un kommunikacios protokoll meghatarozza, hogy egy adott pillanatban veget ert-e mar a kommunikacios folyamat, ha igen, akkor mi a keresett

fuggvenyertek, ha nem, akkor pedig melyik jatekos mondjon egy bitet, es az milyen bit legyen. Hogy mikor ki beszeljen az csak az addig elhangzott bitekt}ol fugghet azert, hogy ne legyen egyszerre beszelesre lehet}oseg. Vegeteres eseten a vegeredmenyt szinten csak az elhangzott bitekt}ol tehetjuk fugg}ove, hiszen ez mindket jatekos szamara ugyanaz kell legyen. Vegul az, hogy ki mit mond az elhangzott bitek, es a szolasra kovetkez}o jatekos inputjanak fuggvenye. Egy P protokoll hossza a leghosszabb bitsorozat hossza, amely az adott protokoll mellet elhangozhat a ket jatekos kozott, azaz ha P (x y ) jeloli a ket jatekos kozott elhangzott bitsorozatot a P protokoll es x, y inputok mellett, akkor jPj = maxx2Xy2Y jP (x y)j. Az f fuggveny kommunikacios komlexitasa pedig a legrovidebb f -et szamolo protokoll hossza, tehat C (f ) = min jPj , ahol a minimalizalas az f -et helyesen kiszamolo protokollokra tortenik. C (f )

lehetseges kiszamtasaval, illetve becslesevel reszletesen most nem foglalkozunk, csak nehany alapvet}o tenyt jegyezzunk meg: 1.1 TE TEL: Amennyiben az inputok n bitesek, akkor C (f )  n + 1 Bizonytas: A trivialis protokollal pl. A egyszer}uen elkuldheti az egesz x-et B-nek, aki gy kiszamthatja f (x y)-t es egyetlen bittel A-t is tajekoztathatja az eredmenyr}ol.  1.2 DEFINICIO : Az f : X  Y ;! f0 1g fuggveny kommunikacios matrixa az az Mf matrix, melynek sorait X , oszlopait Y elemeivel azonostjuk, es x 2 X y 2 Y eseten (Mf )xy = f (x y) 1.3 DEFINICIO : Az Mf matrix egy reszmatrixa monokromatikus, ha a reszmatrix minden eleme azonos. Ekkor a reszmatrixnak megfelel}o X   Y   X  Y halmazt is (az f -re nezve) monokromatikusnak mondjuk. 1.4 TE TEL: Ha az f fuggveny Mf matrixanak monokromatikus reszmatrixokkal valo lefedesehez szukseg van legalabb t monokromatikus reszmatrixra, akkor C (f )  dlog te. (Itt is,

es tovabbiakban is mindenhol a logaritmus kettes alapu.) Bizonytas: Minden kommunikacios protokollhoz rendelhetunk egy binaris fat, az un. protokoll fat, melynek csucsait megjeloljuk az A es B bet}uk valamelyikevel aszerint, hogy az adott pillanatban az A vagy a B jatekos kovetkezik szolasra. A csucsbol kiindulo ket elre nullat illetve egyet runk, es attol fugg}oen, hogy a szolasra kovetkez}o jatekos milyen bitet mond, a megfelel}o iranyba megyunk tovabb. A protokoll fa leveleiben a protokoll veget er, tehat a jatekosok tudjak a vegeredmenyt. Azon (x y) inputparokra, melyekre egy rogztett 3 ` levelben kotunk ki, az f (x y) ezert ugyananazt az erteket adja, jeloljuk ezen inputparok halmazat a tovabbiakban R`-lel. Az R` egy reszmatrixa Mf -nek ugyanis amikor az A (illetve B) jatekos elkuld egy bitet, ezzel az Mf -b}ol bizonyos sorokat (illetve oszlopokat) kizar, a szamara lehetseges inputpok halmaza pedig a

maradekra korlatozodik. Az Mf ilyen fugg}oleges es vizszintes szabdalasaval valoban egy reszmatrix keletkezik. Vagyis R` az Mf matrixban egy monokromatikus reszmatrixot ad, gy a protokoll fa levelei az Mf et monokromatikus reszmatrixokra partcionaljak. Ha a tetel feltetele teljesul, akkor a protokoll fanak legalabb t levele kell legyen, ami egy binaris fa eseten csak ugy lehetseges, ha a melysege legalabb dlog te.  1.5 DEFINICIO : Az f : X  Y ;! f0 1g fuggvenyre egy T = f(xi  yi ) : i 2 f1 : : : tgg  X  Y un. t meret}u becsapos halmaz, amennyiben (1) f (xi  yi ) = z 8i 2 f1 : : :  tg , ahol z 2 f0 1g rogztett, tovabba (2) ha (xi  yi ) (xj  yj ) 2 T , es i 6= j ,akkor f (xi  yj ) = z es f (xj  yi ) = z kozul legalabb az egyik igaz, ahol z = 1 ; z a z negaltja. 1.6 TE TEL: Ha az f fuggveny Mf matrixa tartalmaz t meret}u becsapos halmazt, akkor C (f )  dlog te. Bizonytas: Vegyuk eszre, hogy egy becsapos

halmaz semely ket eleme nem lehet az f fuggveny Mf matrixanak ugyanabban a monokromatikus reszmatrixaban. Ebb}ol az 14 Tetel felhasznalasaval konnyen adodik a tetel.  1.7 TE TEL: Ha az f fuggveny matrixa Mf , akkor C (f )  log rangMf Bizonytas: Ha az MPf matrixot t darab monokromatikus reszmatrixra partcionaljuk, akkor az Mf el}oall Mf = ti=1 Mi alakban, ahol Mi az i-edik monokromatikus reszmatrixa Mf -nek, kib}ovtve nullakkal a reszmatrixon kvul. Azaz  (x y) az i-edik monokromatikus reszmatrixban van (Mi )xy = (0Mf )xy ha egyebkent. Kihasznalva, hogy rang (Mi )  1 P es trang(A + B)  rang(A) + rang(B) , azt kapjuk, hogy P t rang(Mf ) = rang( i=1(Mi ))  i=1 rang(Mi )  t. Amib}ol az 14 Tetellel kovetkezik a kvant eredmeny.  Az altalanostas lehet}osegei Amennyiben a Yao fele kommunikaciot szeretnenk tobb szerepl}ore kiterjeszteni, tobb lehet}oseg is knalkozik az altalanostasra. Nezzunk most vegig egy

parat ezen alternatvak kozul. Amikor a kommunikacioban tobb jatekossal dolgozunk, a legfontosabb, amit el kell dontenunk, hogy a szerepl}ok kozott mikent zajlik a kommunikacio. Beszelhetunk szemelyes kommunikaciorol, amikor mindig csak ket szerepl}o beszelhet egymassal. Ekkor arrol is kell nyilatkoznunk, hogy mely jatekos-parok kozott; enged  unk meg informacioaramlast. Ez azt jelenti, hogy mondjuk k darab jatekos eseten a k2 jatekos-par mindegyiker}ol el kell donteni, hogy letestunk-e kozottuk kapcsolatot. Ezekkel a dontesekkel tulajdonkeppen egy grafot denialunk a k szerepl}on, mint csucsokon ugy, hogy a graf elein engedjuk meg a kommunikaciot. Ekkor meg}orizzuk a Yao fele ketszerepl}os modellnek azt a tulajdonsagat, hogy 4 a kommunikacio ket jatekos kozott zajlik. Ha viszont a ketszerepl}os modellb}ol inkabb azt szeretnenk atvinni a tobbszerepl}os modellbe, hogy egy elkuldott bitr}ol minden

jatekosnak tudomasa van (ami nyilvan teljesul a ketszerepl}os modellben) , akkor egy un. tablas kommunikaciot kapunk, amelyben a szolasra kovetkez}o jatekos mindig egy bitet r fel egy olyan kepzeletbeli tablara, melynek tartalmat az osszes jatekos lathatja. Az el}obbi modellben egy bit elkuldesenek aran csak egy, mg utobbiban az osszes jatekos hozzajut a bitben megtestesul}o informaciohoz, gy nyilvanvalo, hogy ugyanazon fuggveny kiszamtasa az utobbi modellben joval konnyebb, azaz kevesebb (vagy legalabbis nem tobb) bit elkuldeset teszi szuksegesse. A ket lehet}oseg akar keverhet}o is egymassal, gy lehetnek egyszerre ket szerepl}o kozotti kapcsolatok es a jatekosok bizonyos reszhalmazaihoz rendelt tablak is a modellben, ami tulajdonkeppen azt jelenti, hogy a graf, amellyel meghatarozzuk a szerepl}ok kozotti kapcsolatokat egy hipergraf, ahol a 2-nel tobb csucsot tartalmazo elek a megfelel}o tablak.

Ez utobbi eset viszont annyira bonyolult, hogy nem fogunk vele reszletesebben foglalkozni. Hasonloan az el}obbihez arrol is dontenunk kell, hogy a ketszerepl}os modellb}ol azt a tenyt vigyuk at, hogy az osszes szerepl}o rendelkezik sajat inputtal, vagy azt, hogy pontosan ket szerepl}o rendelkezik inputtal. Utobbi esetben az uj jatekosoknak nem adunk inputot, }ok egy kezdeti, ures allapotbol indulnak. Szinten tobbfele lehet}oseg knalkozik az altalanostasra aszerint, hogy egy-egy inputreszt hany jatekos szamara teszunk hozzaferhet}ove. Ez a kerdes termeszetesen a ketszerepl}os modellben fel sem vet}odott, azonban ha 2-nel tobb szerepl}o rendelkezik inputtal, akkor egy inputot nem feltetlenul csak egy jatekosnak adhatunk ki. Meghatarozhatjuk minden egyes inputreszhez, hogy a jatekosok mely csoportjanak adunk ehhez hozzaferesi jogot. Ennek egy igen szels}oseges esetevel fogunk talalkozni a 3 fejezetben, ahol egy-egy

jatekosnak majdnem az osszes inputreszhez lesz hozzaferesi lehet}osege. Vegyuk eszre, hogy nem sok ertelme lenne a tablas kommunikaciot azzal az esettel kombinalni, amikor csak ket szerepl}o rendelkezik inputtal, hiszen ez a jol ismert ketszerepl}os kommunikacios modellt adna vissza, nehany uj jatekossal kiegesztve, akiknek viszont semmi beleszolasa nem lenne az esemenyekbe. A Yao fele kommunikacio lenyeges tulajdonsaga, hogy nem az id}ot tekinti lenyegesnek, hanem csak az elkuldott bitek szamat, ugyanis korlatlan szamtasi lehet}oseget biztost a ket jatekosnak. Ezt szeretnenk atvinni mindenkeppen a tobbszerepl}os modellekre is E ppen ezert a szemelyes kommunikacion belul csak az ugynevezett aszinkron modellekkel fogunk foglalkozni, melyekben az id}o semmilyen szerephez nem jut. Lehet}oseg lenne ugyanis szinkron modelleket is vizsgalni, ahol ugyan a korlatlan szamtasi lehet}oseget meghagynank, de a sok kapcsolaton

elhangzo bitek kozott valamilyen egyidej}useget, es egymasutanisagot neznenk. A celunk tehat az id}ofogalom teljes kikuszobolese, mint azt a linearis halozat modelljenek pontos denciojan keresztul jol fogjuk majd latni. Az aszinkronitas biztostasa azonban meg nem teszi egyertelm}uve, hogy milyen felteteleket szabjunk a megengedett protokolloknak. Az egyszerre beszelest, es egyeb zavarokat a legegyszer}ubben ugy kuszobolhetjuk ki, ha az, hogy mikor ki kovetkezik szolasra csak a kapcsolatokon addig elhangzott bitek fuggvenye. Ez meg is felelne a ketszerepl}os modellben hasznalt protokollfogalomnak. Viszont ha egy tobbszerepl}os modellben egy x inputhoz tobb jatekosnak is van hozzaferese, akkor az, hogy kozuluk ki lesz a kovetkez}o bitkuld}o 5 fugghet akar az x inputtol is anelkul, hogy ez zavarokat okozna. Lathato tehat, hogy szamtalan fajta tobbszerepl}os modellt lehet denialni. A kovetkez}okben ket igen

elter}o modellt fogunk reszletesen megvizsgalni A 2 fejezetbeli linearis halozat szemelyes kommunikacion alapul, es csak ket szerepl}o rendelkezik sajat inputtal, mg a 3. fejezetbeli ,,homlokra ragasztott szam" modellben a kommunikacio tablas, es inputja minden jatekosnak van meghozza ugy, hogy a hozzaferes is eleg kulonos, ugyanis egy jatekos majdnem minden inputot lat. Ezek utan pedig megnezunk egy uj lehet}oseget, a csillag modellt, ami mindket el}obb emltett modellel tartalmaz nehany kozos vonast, es jelen szakdolgozat uj kutatasi temajat kepezi. 6 2. A linearis halozat A modell Egyik lehetseges modja a tobbszerepl}os kommunikacios modell denialasanak, ha a Yao fele ketszerepl}os modellt b}ovtjuk ki tovabbi szerepl}okkel, akiknek azonban nem adunk inputreszt. Tehat tovabbra is csak ket kit}untetett jatekos rendelkezik az x 2 X , illetve y 2 Y inputtal, es egy ketvaltozos f : X Y ;! f0 1g

fuggvenyt szandekoznak kiszamtani. Viszont tobb uj szerepl}o is bekapcsolodik a jatekba ugy, hogy a szerepl}okre, mint pontokra illesztett G graal meghatarozzuk, hogy ki kivel beszelgethet. Egy kommonikacios folyamat hosszat az egyes kapcsolatokon (grafeleken) elhangzott bitek szamainak osszegevel denialhatjuk. Egy f -re adott protokoll hossza termeszetesen a leghosszabb el}ofordulo kommunikacio hossz a lehetseges (x y) inputok mellett, es az f kommunikacios kompexitasa a G graf altal meghatarozott kommunikacios modellben gy CG(f ) = minP jPj , ahol P megengedett protokoll f szamolasara a G graal adott tobbszerel}os modellben. Amennyiben a G grafot egy k hosszu utnak valasztjuk a ket kit}untetett jatekos kozott, akkor a P. Tiwari altal felvetett linearis halozathoz jutunk E modellben tehat k +1 jatekos (P0  P1 : : :  Pk ) vesz reszt. P0 x-et, Pk y-t ismeri, a tobbi jatekosnak nincsen semmilyen informacioja. A

jatekosok egy utat alkotnak, tehat kapcsolata Pi-nek csak Pi;1 -gyel es Pi+1-gyel van. (A kituntetett P0-nak es Pk -nak persze csak egy beszelget}opartnere van) Az f (x y)-t kommunikacios komplexitasat e modellben jelolje Ck (f ). 1.abra Vegyuk eszre, hogy akarmilyennek is valasztanank a G grafot ekvivalens problemat kapnank a linearis halozat modellel, hiszen a ket inputtal rendelkez}o jatekosnak az aszinkron modellunkben kizarolag a koztuk lev}o legrovidebb ut menten lesz celszer}u kommunikalni. Yao mar korabban felvetette e modell valamivel egyszer}ubb valtozatat, amelyben a kommunikacio csak az egyik iranyban zajlik, tehat a kisebb index}u jatekostol a nagyobb index}u fele. E modellben az id}o kizarasa egyaltalan nem jelent gondot, nem ugy, mint a Tiwari fele ketiranyu modellben. Nagyon fontos ezert, hogy utobbit pontosan denialjuk A Yao fele egyiranyu halozatot is meg fogjuk vizsgalni, de most nezzuk meg

hogyan kell a ketiranyu modellt jol, tehat aszinkron modon denialni: Tekintsuk ugy az x y inputokat, mintha azok a virtualis nulladik illetve (k + 1)-edik kapcsolaton hangzananak el rogton a kommunikacio kezdetekor. Egy adott pillanatban si vel jeloljuk az i-edik kapcsolaton addig elhangzott bitek sorozatat Egy a linearis halozatra adott protokoll tobb reszb}ol all. Tartalmaz minden kapcsolathoz egy-egy protokoll fat, mely, akar a ketszerepl}os modellben meghatarozza a ket szerepl}o kozotti kommunikacio lefolyasat. Azaz megadja, hogy mikor melyik jatekos kovetkezik szolasra az adott kapcsolaton, illetve ha a kommunikacio mar veget ert az adott kapcsolaton, akkor mi az eredmeny Mindezeket persze az adott kapcsolaton addig elhangzott bitek fuggvenyeben mondja meg. Tartalmaz tovabba minden 1  i  k -hoz (azaz minden kapcsolathoz) ket fuggvenyt, ezek +i  ;i : f0 1g  f0 1g ;! f0 1 ?g 7 +i : (si;1  si ) 7;! +i (si;1 

si )  ;i : (si  si+1 ) 7;! ;i (si  si+1 ) : Ezek a fuggvenyek megmondjak, hogy az i-edik kapcsolaton balrol, illetve jobbrol milyen bitet kuldjon Pi;1 illetve Pi jatekos. A ? azt jelenti, hogy most nem kuldhet bitet Ez lehet azert, mert ezen a kapcsolaton nem }o kovetkezik szolasra, vagy akar azert, mert meg tovabbi biteket var a masik oldalrol, miel}ott eldonti, hogy milyen bitet kuldjon erre az oldalra. Amennyiben peldaul +i (si;1  si ) = 1, akkor a Pi;1 ezt az egyes bitet elkuldheti Pi -nek most, vagy akarmikor a kes}obbiekben. Ha megfelel}o felteteleket szabunk egy protokollnak, akkor ezek biztostani fogjak, hogy ez ertelmes legyen, ne tudjon megallni, es valoban aszinkron legyen. Ezek a feltetelek a kovetkez}ok: (1) Konzisztencia a protokoll fakkal: Ha az i-edik kapcsolathoz rendelt protokoll fa adott pillanatban egy Pi -vel megjelolt csucsban, vagy egy levelben van, akkor e pillanatban a +i (si;1  si ) = ? (azaz Pi;1 nem

szolhat), hasonloan fordtva. (2) Nincs szandekos blokkolas: (a) Ha az i;-edik, es (i + 1)-edik kapcsolaton + (1  i < k) egyarant Pi kovetkezik szolasra, akkor i (si  si+1 ), es i+1(si  si+1 ) kozul legalabb az egyik nem ?. (b) Ha az i-edik (0  i < k)kapcsolaton+a kommunikacio befejez}odott, es az i +1-edik kapcsolaton Pi kovetkezik szolasra, akkor i+1(si  si+1) 6= ?. Hasonloan a masik oldalra (3) Senki sem gondolhatja meg magat: Ha +i (s+i;1  si ) 6= ? (1+  i  k), tovabba az si;1 = si;1 ti;1 az si;1 meghosszabtasa, akkor i (si;1  si ) = i (si;1  si ). (4) Egyhangusag: Ha a protokoll befejez}odott, akkor a k kapcsolathoz tartozo protokoll fak azonos eredmenyt jelent}o levelben kotottek ki. Ez a protokoll altal kiszamolt eredmeny. Ha a modellt a fenti feltetelekkel denialjuk, akkor egyszer}uen igazolhato a most kovetkez}o lemma, ami minden tovabbi eredmenyhez nelkulozhetetlen. 2.1 LEMMA: Adott protokoll egy adott

(x y) input mellet midig lefuttathato, es minden lefuttatasa eseten ugyanazokat a kommunikaciokat eredmenyezi minden egyes kapcsolaton. A kes}obbiekben gyakran szuksegunk lesz a kovetkez}o lemmara, ami a 2.1 Lemma teljesulese miatt nem kvan bizonytast. 2.2 LEMMA: Amennyiben rogztunk egy kapcsolatot, pl az l-ediket (1  l  k), ugy a halozatnak megfeleltethetunk egy ketszerepl}os kommunikacios modellt, melyben az A jatekos szimulalja a fP0 P1  : : :  Pl;1 g, a B pedig a fPl Pl+1 : : :  Pk g jatekosok tevekenyseget. Ekkor az l-edik kapcsolaton elhangzott bitsorozat a halozatban, es a ketszerepl}os modell kommunikacios bitsorozata megegyezik. Az 1. fejezetben a ketszerepl}os kommunikacios modell denialasakor mar tisztaztuk, hogy az, hogy mikor ki beszel az csak az addig elhangzott bitekt}ol fugg. Ennek kovetkezmenye, hogy azon bitsorozatok, melyek elhangozhatnak a ket szerepl}o kozotti kommunikacio soran egy un

prex-mentes halmazt alkotnak, azaz a halmaznak nem lehet ket olyan eleme, hogy az egyik a masik prexe (kezd}oszelete). Ugyanis ha lenne ket ilyen 8 bitsorozat, akkor a rovidebbik elhangzasa utan nem lenne egyertelm}u mindket jatekos szamara, hogy veget ert a kommunikacio, vagy esetleg egyikuk meg szolasra kovetkezik. Ha ezt a gondolatmenetet a linearis halozat ketszerepl}os szimulaciojaval egyutt hasznaljuk, az alabbi fontos lemmat kapjuk: 2.3 LEMMA: A linearis halozat tetsz}oleges kapcsolatat rogztve, a kulonboz}o inputok mellett az ezen kapcsolaton elhangzo bitsorozatok egy prex-mentes halmazt alkotnak Egy ilyen halmazrol a kovetkez}ot tudjuk: 2.4PtLEMMA: Ha S = fs1  s2  : : :  st g egy prex-mentes reszhalmaza f0 1g -nak, akkor j=1 jsj j  t log t. Bizonytas: Minimalizaljuk adott t mellett a Ptj=1 jsj j (osszhossz) erteket, amikor S = fs1  s2 : : :  st g prex-mentes halmaz. Amennyiben leteznek i j 2 f1 2 : : :

 tg indexek, hogy sj legalabb 2 bittel hosszabb si -nel, akkor si  sj elhagyasaval, es helyettuk si 0 valamint si 1 bitsorozatok S -be bevetelevel az osszhossz nem n}o, viszont a hosszak negyzetosszege csokken. Ezert az osszhossz a minimumat biztosan felveszi olyan S halmaz mellett, amelyre az si -k hosszai kozotti elteresek maximuma 1. Legyen tehat most S ilyen Ebben az esetben a legrovidebb bitsorozathosszusagok, amik el}olfordulhatnak azok blog tc es blog tc + 1, ennel r}ovidebb elemekb}ol ugyanis biztosan nem lehet egy t elem}u prex-menets halmazt osszealltani. Jelolje c, hogy hany blog tc hosszu szo van, ekkor persze a blog tc + 1 hosszu szavak szama t ; c. Az osszhossz minimalizalasa most mar csak a c maximalizalasat jelenti. Egyreszt nyilvan c  2blog tc, masreszt viszont egy blog tc hosszu szo kizarja ket blog tc +1 hosszu szo S -be kerulesenek lehet}oseget (azt a kett}ot, amelyeknek }o prexe), gy kapunk egy masik

feltetelt is c-re, meghozza azt, hogy legalabb annyi szobajohet}o blog tc+1 hosszu szo marad, amennyi kell, azaz t ; c  2blog tc+1 ; 2c. Ez atalaktva c  2blog tc+1 ; t Viszont konnyen latszik, hogy a masodik feltetel mindig er}osebb (2blog tc  2blog tc+1 ; t). Az optimum tehat c = 2blog tc+1 ; t. Ebb}ol az optimalis osszhossz cblog tc + (t ; c)(blog tc + 1) = (2blog tc+1 ; t)blog tc ; 2blog tc+1 (blog tc + 1) = = tblog tc + 2(t ; 2blog tc ) P Ez tehat a tj=1 jsj j minimalis erteke. Hogy ez nagyobb t log t -nel az pedig abbol latszik, hogy amennyiben t egy 2-hatvany, akkor lathatoan egyenl}oseg all fenn. Ket szomszedos 2-hatvany kozott viszont blog tc allando, gy a minimalis ertek e darabon linearis fuggveny, mely mivel a t log t fuggveny konvex (masodik derivaltja pozitv), ezert a t log t fuggvenygorbeje felett halad. Yao egyiranyu halozata Az egyszer}useg kedveert nezzuk el}oszor a Yao altal vizsgalt specialis

esetet a linearis halozatnak, amikor a jatekosok kozotti kapcsolatok csak egyiranyuak, tehat amikor Pi a Pi+1-nek tud kuldeni informaciot, de fordtva nem. Ekkor termeszetesen csak azt kvanjuk meg egy protokollrol, hogy a vegere Pk tisztaban legyen az f (x y) ertekkel. Ebben az 9 esteben a kovetkez}o pontos eredmenyt tudjuk, ha Ck!(f )-val jeloljuk e modellben a kommunikacios komplexitast: 2.5 TE TEL: Ha Mf -nek pontosan t kulonboz}o sora van, akkor dk log te  Ck! (f )  k dlog te: Bizonytas: A fels}o becsles trivialis, hisz P0 -nak csak az inputnak megfelel}o sor szamat kell vegigkuldenie a halozaton. Nezzuk tehat az also becslest: Legyen x1 x2  : : :  xt olyan t input, melyekhez tartozo Mf -beli sorok paronkent kulonboz}oek. Jelolje sl (i) azt a bitsorozatot, amely az l-edik kapcsolaton (Pl;1 es Pl kozott) hangzik el, ha P0 inputja xi . Az egyiranyu adagyovabbtas kovetkezteben ez tenyleg csak a P0 -nal

lev}o inputtol fugg. Az, hogy xi es xj sora kulonbozik Mf -ben azt jelenti, hogy letezik olyan y 2 Y , melyre f (xi  y) 6= f (xj  y). Ha sl(i) = sl (j ) lenne valamely l i j ertekekre, akkor f (xi  y) = f (xj  y) allna 8y 2 Y mellett, ami viszont ellentmondas. Ezert sl (i) 6= sl(j ) kell legyen minden l i j eseten, azaz egy rogztett kapcsolaton athalado bitsorozat minden kulonboz}o xi inputra mas es mas. Az fsl (i) : 1  i  tg halmaz gy t kulonboz}o bitsorozatbol all, es azt is tudjuk (2.3 Lemma), hogy prex-mentes halmaz, ebb}ol a 24 Lemma alkalmazasaval adodik, hogy t X k X P j =1 l=1 jsl (j )j = k X t X l=1 j =1 jsl (j )j  k X l=1 t log t = k t log t: Ahol kl=1 jsl (j )j eppen a teljes kommunikacio hossza az xj input mellett, gy a bal oldalon allo kifejezes nem mas, mint a kommunikaciok hosszainak osszege a kulonboz}o xj inputok mellett. Ezert az erre kapott also becslesunkb}ol skatulya-elvvel kovetkezik, hogy

letezik olyan j , melyre a kommunikacio hossza  dk log te.  Tiwari sejtese Terjunk most vissza a Tiwari fele halozati modellhez, ahol mindket iranyban zajlik a kommunikacio. Amennyiben a linearis halozatban a kozbuls}o, tehat inputtal nem rendelkez}o jatekosoknak csak azt a feladatot adjuk, hogy tovabbtsak az informaciot a ket kituntetett jatekos kozott, akkor az gy kapott protokoll tulajdonkeppen egy ketszerepl}os kommunikacio azzal a kulonbseggel, hogy egy bit elkuldese helyett ugyanezt k-szor kell megtenni. Ebb}ol az adodik, hogy Ck (f )  k C (f ) , ahol C (f ) az f hagyomanyos (ketszerepl}os) kommunikacios komplexitasa. Segthetnek-e a kozbuls}o jatekosok ennel hatekonyabban egy fuggveny kiszamtasaban, azaz szigoru-e az egyenl}otlenseg, amit az el}obb felrtunk? Vagy talan egyenl}oseg all, es semmilyen mas protokoll nem jobb az egyszer}u adattovabbtasnal? E fejezetben be fogjuk bizonytani a

kovetkez}o, Tiwaritol szarmazo (ld. 2]) tetelt: 2.6 TE TEL: Majdnem minden f fuggvenyre teljesul, hogy Ck (f )  k(C (f ) ; 1) A majdnem minden szot ugy kell erteni, hogy egy veletlenszer}uen valasztott f : f0 1gn f0 1gn ;! f0 1g fuggvenyre 1-hez tarto valoszn}useggel igaz a tetel (n ! 1). 10 Ebb}ol Tiwari azt sejtette, hogy a 2.6 Tetel minden f fuggvenyre fennall Hogy a sejtes nem igaz, azt kes}obb latni fogjuk, most azonban igazoljuk a 2.6 Tetelt A tovabbiakban az egyszer}useg kedveert az X Y inputalaphalmazok a f0 1gn legyenek. Mint azt az 1.6 Tetelben lattuk, az f fuggveny kommunikacios matrixaban egy becsapos halmaz jelenlete lehet}oseget adott C (f ) also becslesere Hasonlot allthatunk a linearis halozaton: 2.7 TE TEL: Ha az f fuggveny Mf matrixa tartalmaz t meret}u becsapos halmazt, akkor C (f )  dk log te. Bizonytas: Legyen T = f(xi  yi ) : 1  i  tg egy t meret}u becsapos halmaz Mf ben, es

jelolje sl (i) az l-edik kapcsolaton elhangzott bitsorozatot az (xi  yi ) input mellett. Az l-edik kapcsolat menten vehetjuk a ketszerepl}os szimulaciojat a halozatnak (22 Lemma). Ebb}ol ha sl(i) = sl (j ) allna fenn valamilyen i j 2 f1 : : :  tg mellett, akkor f (xi  yi ) = f (xi  yj ) = f (xj  yi ) = f (xj  yj ) lenne, ami ellentmond annak, hogy T egy becsapos halmaz. Itt tulajdonkeppen egy a kes}obbiekben kimondando lemma (210 Kicserelesi lemma) specialis esetet alkalmaztuk. Ebb}ol rogztett l-re az sl(i) bitsorozatok minden ire kulonboz}oek, innen pedig a bizonytas vege egy az egyben a 25 Tetel bizonytasanak vegevel egyezik meg.  Ez azt jelenti, hogy egy kell}oen nagy becsapos halmaz jelenlete Mf -ben azt eredmenyezi, hogy C (f ) n-hez, Ck (f ) pedig kn-hez lesz kozeli, ebb}ol kovetkez}oen Tiwari sejtese igaz, ha megfelel}oen nagy (2n-hez kozeli) meret}u becsapos halmaz letezik Mf -ben. Mivel azonban egy altalanos f -re

leggtobbszor nem mutathato ki egy ilyen nagy becsapos halmaz jelenlete, gy a log-rang modszer iranyaba fogunk tovabbmenni, el}obb azonban egy kis el}okesztesre lesz szukseg. 2.8 DEFINICIO : Legyen P egy protokoll az f (x y) fuggveny kiszamtasara a linearis halozaton. A P kommunikacios grafja az a GP graf, melyet a kovetkez}okeppen kapunk: Jelolje Sl bitsorozatok azon halmazat, melyek valamilyen (x y) input mellett elhangozhatnak az l-edik kapcsolaton. Tekintsuk ugy, hogy az x illetve y inputok a P0 illetve Pk jatekosok szamara a kepzeletbeli nulladik illetve (k + 1)-edik kapcsolaton hangzanak el. Ekkor GP pontjai k + 2 halmaz elemei. E halmazok: X = S0 S1 S2  : : :  Sk  Sk+1 = Y GP egy szintezett graf az Sl halmazokkal (0  l  k + 1), mint szintekkel, elek csak a szomszedos szintek, tehat Sl es Sl+1 kozott vezetnek. Az Sl es Sl+1 kozotti elek halmaza, El a kovetkez}okeppen van denialva (l 2 f0 1 : : :  kg) : El =

f(sl  sl+1) : Letezik (x y) 2 X  Y , hogy f (x y) = 1 es sl  sl+1 megjelennek, mint kommunikacio az l-edik illetve (l +1)-edik kapcsolatokon az f (x y) szamtasa kozbeng 2.abra 2.9 DEFINICIO : A GP grafban ,,hosszu ut"-nak nevezunk egy k + 1 el}u utat, mely az X = S0 halmaz egy x elemet koti ossze az Y = Sk+1 halmaz egy y elemevel, es minden Sl halmazbol pontosan egy elemet erint. Vilagos, hogy amennyiben f (x y) = 1, ugy (x y) input mellett a protokoll futtatasa utan a kapcsolatokon megjelen}o bitsorokkal mint koztes pontokkal egy ,,hosszu ut" van 11 GP -ben x es y kozott. Ennek viszont a megfordtasa is igaz, mint azt a 211 Tetelben latni fogjuk. El}obb azonban kovetkezzek egy nagyon fontos lemma: 2.10 LEMMA (KICSERE LE SI LEMMA): Ha az (x y) es (x  y ) inputparok eseten a P protokoll mellett a kapcsolatokon rendre az (s1  s2  : : :  sk ) illetve a (s1  s2  : : :  sk ) bitsorozatok jelennek meg a

kommunikacio soran, es az l-edik kapcsolaton ugyanaz az sl = sl jon letre, akkor az (x y ) inputpar mellett az (s1  s2  : : :  sl;1  sl sl+1  : : :  sk ) fog a kapcsolatokon letrejonni. Bizonytas: A lemma alltasa egyszer}uen kovetkezik abbol, hogy az l-edik kapcsolattol balra lezajlo kommunikaciok csak az l-edik kapcsolaton elhangzo bitekt}ol, es a P0 jatekosnal lev}o inputtol fuggenek. Mivel a lemma feltetelei mellett mindkett}o azonos az (x y) es (x y ) inputparok eseten, gy az els}o l ; 1 kapcsolaton ugyanaz a bitsorozat kell elhangozzon a ket inputpar mellett. Ugyangy az l-edik kapcsolattol jobbra lev}o kapcsolatokon az (x y ) es az (x  y ) inputparok eredmenyezik ugyanazt a kommunikaciot Hasonlo gondolatmenettel igazolhato, hogy az (x  y) inputpar pedig az (s1  s2  : : :  sl;1 sl  sl+1 : : :  sk ) bitsorozatokat eredmenyezi a kapcsolatokon.  2.11 TE TEL: GP -ben letezik egy ,,hosszu ut" x

2 X es y 2 Y kozott fsl : l = 1 : : :  k g koztes pontokkal () f (x y ) = 1 es f (x y ) kiszamtasa soran az ledik kapcsolaton sl a kommunikacios bitsorozat. Bizonytas: A (= iranyt mar lattuk, gy mar csak a =) iranyt kell megmutatnunk. Az, hogy letezik egy ,,hosszu ut" x es y kozott fsl : l = 1 : : :  kg koztes pontokkal dencio szerint azt jelenti, hogy leteznek (xi  yi ) parok (i = 0 1 2 : : :  k), hogy f (xi  yi ) = 1 , x0 = x , yk = y es f (xi  yi ) szamtasa mellett si es si+1 lesz a kommunikacio az iedik illetve (i + 1)-edik kapcsolaton. Teljes indukcioval megmutatjuk, hogy minden j -re (j=0, 1, 2, : : : , k) igaz, hogy f (x yj ) szamolasanal az l-edik kapcsolaton sl a kommunikacio minden 1  l  (j + 1) eseten. Az indukcios alltas y0 valasztasa miatt igaz j = 0-ra Ha igaz (j ; 1)-re, akkor f (x yj;1 ) szamtasanal az els}o j kapcsolaton a kvant kommunikacio hangzik el, mg f (xj  yj )

szamtasanal azt tudjuk, hogy a j -edik es (j +1)-edik kapcsolaton sj illetve sj+1 a bitsorozat. Ebb}ol a kicserelesi (210) Lemmaval kovetkezik, hogy f (x yj )re mar az els}o (j + 1) kapcsolaton az sl -ek hangzanak el A j = k esteben (amely eppen igazolja a tetelt) a bizonyitas csak annyiban kulonbozik , hogy nincs (k +1)-edik kapcsolat.  2.12 KO VETKEZME NY: Legfeljebb egy ,,hosszu ut" vezethet GP barmely ket pontja kozott. Bizonytas: A 2.11 Tetel es a 21 Lemma kozos kovetkezmenye  Jelolje Ai a GP graf Si  Si+1-re valo megszortasaval letrejov}o paros graf adjacencia matrixat. Akkor: 2.13 LEMMA: Mf = A0 A1 : : : Ak Bizonytas: Jelolje B := A0 A1 : : : Ak , akkor Bxy = X s1 s2 :::sk A0xs1 A1s1 s2 : : : Aksky : 12 Az osszegben egy nem-nulla elem egy ,,hosszu ut"-nak felel meg x es y kozott, gy a 2.11 Tetellel es 2.12 Kovetkezmennyel Bxy = (Mf )xy  2.14 LEMMA: Legyen Amm a G paros graf

adjacencia matrixa Ha A nem szingularis a valos test felett, akkor G-ben van teljes parostas. Bizonytas: Az A valos test feletti permanense, per(A) megadja a G-ben lev}o teljes parostasok szamat. Az A nem szingularis , azaz det(A) 6= 0 , gy az A 0=1 matrix volta miatt ez azt jelenti, hogy per(A) > 0, ebb}ol pedig G-ben letezik legalabb egy teljes parostas.  2.15 TE TEL (BINET-CAUCHY): Legyen Amm = Bmk Ckm es legyen k  m. Akkor X det(A) = det(B(S ))det(C (S )) S f12:::kgjS j=m ahol B(S ) (ill. C (S )) a B (ill C ) azon reszmatrixa, melyet az S altal megjelolt oszlopok (ill. sorok) kivalasztasaval nyerunk Bizonytas: Megtalalhato pl. 11]-ben  2.16 KO VETKEZME NY: Ha A = BC nem szingularis, akkor van egy S  f1 2 : : :  kg es jS j = m, hogy B(S ) es C (S ) is nem szingularis. Jelolje Gi (i = 0 1 2 : : :  k) azt a paros grafot, melyet a GP graf Si  Si+1 halmazra valo megszortasaval nyerunk. Ennek adjacencia

matrixa Ai , mint mar emltettuk Jelolje Bj := A0A1 : : : Aj . Mint lattuk a 213 Lemmaban : Bk = Mf Most X = Y = f0 1gn legyen, ekkor jX j = jY j = 2n. 2.17 TE TEL: Amennyiben Mf nem szingularis, akkor GP -ben letezik 2n darab pontdiszjunkt ,,hosszu ut", melyek mindegyike kulonboz}o X -beli pontbol indul, es kulonboz}o Y -beli pontba erkezik. Bizonytas: Az alltast k-ra (a halozat hosszara) vonatkozo indukcioval bizonytjuk. A k = 0 eset ugyan valojaban nem letezik, megis ez lesz az indukcio kiindulopontja. Ekkor a kepzeletbeli GP -nek ket szintje lenne X es Y , azaz paros graf lenne. Ekkor ha B0 = A0 nem szingularis, akkor a 2.14 Lemma szerint a paros grafban letezik teljes (2n meret}u) parostas. Tegyuk fel, hogy k-ra igaz, hogy a k + 2 szinttel rendelkez}o szintezett GP grafra ha a Bk nem szingularis, akkor letezik 2n darab pontdiszjunk ,,hosszu ut" a ket szels}o szint kozott. Ekkor (k +1)-re Bk+1 = Bk Ak+1,

ahol Bk egy 2n jSk+1j meret}u, Ak+1 pedig egy jSk+1j 2n meret}u matrix. Ha B k+1 nem szingularis, akkor a 215 Tetel ertelmeben letezik S  Sk+1 , ahol jS j = 2n es Bk (S ) valamint Ak+1(S ) nem szingularis 2n  2n-es matrixok. Az indukcios felteves szerint letezik 2n darab pontdiszjunkt ut S0 = X es S  Sk+1 kozott. A 2.16 Kovetkezmeny ertelmeben pedig az S es Sk+2 = Y halmazok kozott letezik teljes parostas. Az el}obbi utakat a parostasbali elekkel meghosszabbtva megkapjuk a kvant 2n darab pontdiszjunkt utat X es Y kozott.  2.18 TE TEL: Ha Mf nem szingularis, akkor Ck (f )  kn Bizonytas: Mivel Mf nem szingularis, gy a 2.17 Tetel biztostja, hogy letezik 2n pontdiszjunk ,,hosszu ut" GP -ben. Ha az i-edik ut vegpontjai xi  yi , akkor a T = 13 f(x1  y1 ) : : :  (x2n  y2n )g halmaz 2n olyan inputparbol all, hogy semely kett}onek nem egyezik meg a kommunikacios bitsorozata egyik kapcsolaton sem. A 25

Tetelbeli skatulya-elvvel azonos modon mutathato meg, hogy ekkor letezik egy j , hogy (xj  yj ) mellett az oszes kommunikacio legalabb kn bit.  2.19 KO VETKEZME NY: Ha Mf az f fuggveny matrixa, akkor Ck (f )  k log(rang(Mf )): Bizonytas: Ha Mf nem nem szingularis, akkor a 2.18 Tetelt alkalmazhatjuk a legnagyobb nem szingularis reszmatrixara, amelynek merete rang(Mf )  Mar csak annyit kell megmutatnunk, hogy egy altalanos f fuggveny matrixanak nagy a rangja: 2.20 TE TEL: Majdnem minden n  n-es 0=1 matrix rangja  n ; f (n) GF (2) felett tetsz}oleges olyan f fuggvenyre, mely 1-hez tart n ! 1 eseten. Bizonytas: Becsuljuk alulrol a legalabb r rangu 0=1 matrixok szamat, mr -et, meghozza azon matrixok szamaval, melyek els}o r sora fuggetlen GF (2) felett: Az els}o r sor Q r ; 1 megvalasztasara i=0 (2n ;2i) lehet}oseg van, mg ezek utan a matrixot 2n(n;r) -felekeppen lehet befejezni. Ezert rY ;1 n ( n ; r ) mr  2 (2n ; 2i

): i=0 Az n  n-es 0=1 matrixokbol osszesen 2n2 =: m van. Igy a legalabb r rangu matrixok aranya az osszes matrixok kozott: mr  m Qr;1 r;1 r;1 n i i=0 (2 ; 2 ) = Y (1 ; 1 )  1 ; X 1  1 ; 1 n;i 2nr 2n;i 2n;r i=0 i=0 2 Ez pedig r = n ; f (n) eseten 1-hez tart.  A valos test feletti rang ennel mar csak nagyobb lehet. Arra jutottunk tehat, hogy a fuggvenyek tulnyomo reszere a log-rang becsles nagyon jol becsli C (f )-et es Ck (f )-et egyarant, ezekre a fuggvenyekre ezaltal igaz Tiwari sejtese. A sejtes cafolata Mivel Tiwarinak sikerult bizonytania, hogy majdnem minden f fuggvenyre teljesul, hogy Ck (f )  k(C (f ) ; 1), gy azt sejtette, hogy ez tetsz}oleges f fuggvenyre fennall. A sejtes cafolatahoz olyan fuggvenyt kell konstrualni, melynek kiszamtasahoz a kozbuls}o jatekosok intelligensebb modon is hozzajarulhatnak, mint ha csak biteket tovabbtanak a ket kit}untetett jatekos kozott. Egy ilyen f fuggvenyre

Ck (f )-et felulr}ol, C (f )-et pedig alulrol kell becsulni ahhoz, hogy a sejtest megcafoljuk. E Kushilevitz, N Nisan es R Ostrovsky 3]-ban olyan vegtelen sok fuggvenyb}ol allo osztalyt mutattak, melyre Ck (f )  ( 43 + o(1)) k C (f ): () 14 ahol k tetsz}oleges paros szam, az o(1) hibatag pedig n ! 1 mellett ertend}o. Legyen g : f0 1gn  f0 1gn ;! f0 1g egyel}ore tetsz}oleges fuggveny. Hogy milyen felteteleknek kell eleget tegyen az kes}obb fog majd kiderulni. E g segtsegevel konstrualjunk egy fg -vel vagy egyszer}uen csak f -fel jelolt fuggvenyt a kovetkez}okeppen: 2.21 DEFINICIO : Legyen f : f0 1g2n  f0 1g2n ;! f0 1g az a fuggveny, amelyre x1  x2  y1  y2 2 f0 1gn eseten  g(x1  y1 ) = 1 f (x1  x2 ] y1 y2 ]) := gg((xx1  yy2 )) ha 2 1 ha g (x1  y1 ) = 0 Azt alltjuk, hogy a lehetseges g fuggvenyek tulnyomo reszere az gy denialt f -re fennall (*), ezt a 2.25 Tetel fogja kimondani Ehhez Ck (f )-et felulr}ol, C

(f )-et pedig alulrol kell megbecsulni. 2.22 TE TEL: A fenti f -re Ck (f )  32 k n + 2k , ha k paros Bizonytas: Adunk egy megfelel}o protokollt a k hosszu linearis halozaton, amennyiben k paros. Kezdetben P0 szamara x1  x2 ], Pk szamara y1 y2 ] ismert Kuldje el P0 az x1 -et, Pk pedig az y1-et a Pk=2 ,,kozeps}o" jatekosnak a fPi : i = 1 2  k2 ; 1g illetve a fPi : i = k2 + 1 k2 + 2  k ; 1g jatekosok tovabbtasaval. Ehhez eddig 2 k2 n bit kommunikaciora van szukseg Ezutan Pk=2 szamtsa ki x1 es y1 ismereteben g(x1  y1 ) erteket Amennyiben g(x1  y1 ) = 1, akkor Pk=2 kuldje el x1-et Pk -nak, gy }o tudja szamolni g(x1  y2 ) (tehat az f ) erteket. Ehhez ujabb k2 n bit szukseges majd a vegeredmenyr}ol Pk minden tovabbi jatekost tajekoztathat k bit kommunikacioval. Hasonloan ha g(x1 y1 ) = 0, akkor Pk=2 kuldje el P0-nak az y1-et, aki gy szamolhatja g(x2  y1 )-et (tehat f -et), stb. Azonban meg miel}ott Pk=2

elkuldi peldaul x1 -et a Pk -nak kuldenie kell egy-egy bitet P0 es Pk jatekosok fele, ezzel tajekoztatva }oket, hogy inputreszt varjanak, vagy csak a vegeredmenyt. Mondjuk az 1-es azt jelenti, hogy az inputresz kovetkezik, a 0 pedig, hogy neki mar nincs mas dolga, mint megvarni az eredmenybitet. Ez meg tovabbi 2 k2 , azaz k bit kommunikaciot jelent Az osszes kommunikacio 32 kn + 2k , ami igazolja a tetelt Paratlan k eseten a 32k helyett mindenhol 3k2+1 lenne irando a bizonytasban, ami egy ujab k-tol fugg}o hibatagot eredmenyezne. Mg a 2.22 Tetel a g valasztasatol fuggetlenul igaz, addig C (f ) alulrol torten}o becslese nem lehetseges akarmilyen g mellett, azonban mint nemsokara kiderul a fuggvenyek legtobbje megfelel}o lesz. Valasszuk egyel}ore veletszer}uen a g fuggvenyt Jelolje N := 2n. Legyenek 0    1 es  1 kes}obb meghatarozando konstansok Jelolje tovabba L := n. A lljon R1 az Mg (a g N  N -es

matrixanak) sorainak L darab diszjunkt parjabol, es ugyangy R2 az Mg oszlopainak L diszjunkt parjabol. Ekkor az R1  R2 tartalmaz L2 darab 2  2-es reszmatrixot Mg -b}ol. Az R1  R2-t nevezzuk -kiegyensulyozottnak, ha a lehetseges 24 = 16 lehetseges 2  2-es reszmatrix mindegyike legalabb L2 -szer el}ofordul R1  R2-ben. Denialjuk a kovetkez}o feltetelt: (F1) Az  = 1=32 ertek mellett az Mg matrix minden 2L  2L reszmatrixa -kiegyensulyozott. 15 2.23 TE TEL: Majdnem minden g fuggvenyre teljesul az (F1) feltetel Bizonytas: Itt most elhagyjuk az egyebkent egyszer}u szamolast igenyl}o bizonytast. Az also becsles folyamatosan hasznalja, hogy g kielegti az (F1) feltetelt, es annak az alabbi kozvetlen kovetkezmenyeit. (F2) Az Mg nem tartalmaz L  L meret}u monokromatikus reszmatrixot. (F3) Az Mg minden 2L  L meret}u reszmtrixaban a lehetseges 4 darab 2  1-es reszmatrix mindegyike legalabb L2-szer el}ofordul.

Hasonlon az Mg minden L  2L meret}u reszmtrixaban a lehetseges 4 darab 1  2-es reszmatrix mindegyike legalabb L2szer el}ofordul. Az Mg egy A  B reszmatrixanak x 2 A sorat B-re nezve -kiegyensulyozottnak mondunk, ha a reszmatrixon belul az x sorban a nullak aranya 8 es 1 ; 8 kozott van. (F4) Ha A  B az Mg reszmatrixa, es jBj  L, akkor A-ban legfeljebb 2L sor nem kiegyensulyozott B-re nezve ( = 1=32). Ugyangy ha jAj  L, akkor pedig B-nek lehet csak legfeljebb 2L A-ra nezve kiegyensulyozatlan oszlopa. 2.24 TE TEL: Ha g eleget tesz az (F1) feltetelnek, akkor a bel}ole nyert f = fg fuggvenyre C (f )  (2 ; o(1)) n. Bizonytas (vazlat): C (f ) alulrol torten}o becslesehez nem hasznalhatjuk az eddig ismert, es alkalmazott technikakat, hiszen olyan f fuggvenyekre, melyek kommunikacios komplexitasat a ,,log-rang" illetve a ,,becsapos halmaz" technikaval jol lehet alulrol becsulni, azokra Tiwari bizonytotta a

sejteset, gy remenytelen, hogy barmelyik modszer m}ukodj}on a sejtest cafolo f -ekre. Tehat mindenkeppen egy uj becslesi technikara van szukseg. Az uj technika lenyege, hogy a fuggvenyre adott tetsz}oleges protokoll fajaban olyan csucs letezeset igazoljuk, melyhez vezet}o ut kell}oen hosszu, es a csucsbol szinten megfelel}oen hosszu ut talalhato a fa egyik levelehez. A sok szamolast igenyl}o bizonytast itt most elhagyjuk, megtalalhato 3]-ban. 2.25 TE TEL: Ha k es n paros, akkor letezik vegtelen sok olyan f : f0 1gn  f0 1gn ;! f0 1g fuggveny, amelyre Ck (f )  ( 34 + o(1)) k C (f ): Bizonytas: Minden g : f0 1gn=2  f0 1gn=2 ;! f0 1g fuggvenyre Ck (fg )  43 k n a 2.22 Tetel ertelmeben A 224 Tetel pedig biztostja, hogy majdnem minden g-re C (fg )  (1 ; o(1)) n. E kett}ob}ol pedig majdnem minden g-b}ol kapott fg -re igaz a tetel A legjobb, minden f -re igaz eredmeny Lattuk, hogy Ck (f ) lehet kisebb kC (f

)-nel, akar egy 3=4-es szorzoval. Jo lenne viszont azt is tudni, hogy legfeljebb mennyivel lehet kisebb. Sokaig a legjobb ismert also becsles Ck (f )-re az alabbi volt: p 2.26 TE TEL: Ck (f ) = (k ( C (f ) ; log k)) 16 Bizonytas: Megmutatjuk, hogy R0(f )  Ck (f ) + log k , ahol k R0(f ) az f randomizalt, 0-hibas kommunikacios komplexitasa a ketszerepl}os modellben. Azaz R0 (f ) az a kommunikacios komplexitas, amit akkor kapunk, ha protokollnak egy a hagyomanyos modon ertelmezett, es az adott fuggvenyt jol kiszamolo protokolokon vett veletlen eloszlast tekintunk, es azgy kapott protokoll hosszan a veletlenszer}uen valasztott hagyomanyos protokoll hossz panak a varhato erteket ertjuk. Mivel ismert (ld pl 12]), hogy R0(f ) = ( C (f )) , gy az alltas mar kovetkezik. Adott protokollhoz a k hosszu linearis halozaton, mely Ck (f ) kommunikaciot hasznal konstrualunk egy ketszerepl}os randomizalt, 0-hibas protokollt a

kovetkez}okeppen: Az A jatekos veletlenszer}uen, egyenl}o valoszn}useggel valaszt egyet a k kapcsolat kozul, mondjuk az l-ediket, es elkuldi l-et B-nek (log k bit). Ezek utan lefolytatjak a halozat ketszerepl}os szimulaciojat az l-edik kapcsolat menten (2.2 Lemma) E protokoll mellett a kommunikacio varhato erteke Ckk(f ) . Tehat valoban R0(f )  Ckk(f ) + log k  Azonban ennel sokkal jobb becslest sikerult adnia M. Dietzfelbingernek 4]-ben Igazolta, hogy letezik konstans, hogy Ck (f )  k C (f ) A problema viszont csak akkor lesz teljesen megoldott, ha sikerul a legnagyobb ilyen -t meghatarozni, a legjobb eddig ismert ertek -ra: 0 275. Nezzunk azonban el}obb nehany nagyon fontos lemmat Szukseg lesz a kicserelesi lemma (2.10) egy egyszer}u, de alapvet}o fontossagu kovetkezmenyere 2.27 LEMMA (KO ZREFOGA SI LEMMA): Ha az (x y) es (x  y ) inputparok eseten a P protokoll mellett a kapcsolatokon rendre az (s1  s2  : : : 

sk ) illetve a (s1  s2  : : :  sk ) bitsorozatok jelennek meg a kommunikacio soran, es az i-edik es j -edik kapcsolaton (1  i  j  k) egyarant ugyanaz az si = si illetve sj = sj jon letre, akkor miden koztes kapcsolaton is megegyezik a kommunikacio, azaz sl = sl 8i  l  j . Bizonytas: A 2.10 Lemmat el}oszor az i-edik kapcsolatra alkalmazva azt kapjuk, hogy (x y ) inputra a kapcsolatokon (s1  s2  : : :  si  si+1 : : :  sk ) lesz. Alkalmazva ismet a 2.10 Lemmat, ezuttal a j -edik kapcsolatra, es az (x y ), (x y) inputokra pedig azt adja, hogy az (x y) eseten meglelen}o bitsorozatok: (s1  : : :  si;1  si  : : :  sj  sj+1  : : :  sk ) , amib}ol az egyertelm}useg miatt (2.1 Lemma) kovetkezik a kvant alltas  A most kovetkez}o lemma kulcsszerepet jatszik az also becslesben: 2.28 LEMMA: Ha P egy protokoll az f kiszamtasara a k hosszu linearis halozaton, akkor f -re van ketszerepl}os protokoll, mely nem tobb,

mint 2jPj=dk=2e kulonboz}o bitsorozatot hasznal. Bizonytas: Legyen k paros az egyszer}useg kedveert. A P indukal egy ketszerepl}os protokollt (2.2 Lemma) a (k=2)-edik kapcsolat menten Tegyuk fel, hogy e ketszerepl}os kommunikacio soran t kulonboz}o bitsorozat hangozhat el. (Azaz a halozat k=2-edik kapcsolatan a P protokoll mellett t bitsorozat hangozhat el.) Megmutatjuk, hogy jPj  (k=2) log t, ami paros k -ra igazolja az alltast. Legyenek (x1  y1 ) (x2  y2 ) : : :  (xt  yt ) olyan inputparok, melyekre a (k=2)-edik kapcsolaton elhangzo bitsorozatok - azaz sk=2 (x1  yP 1 ) sk=2 (x2  y2 ) : : :  sk=2 (xt  yt ) - mind kulonboz}oek. Nyilvanvalo, hogy 1 jPj  t tj =1 js(xj  yj )j , ahol s(xj  yj ) = s1 (xj  yj )s2 (xj  yj ) sk (xj  yj ) , azaz az osszes 17 elhangzott kommunikacio konkatenacioja az (xj  yj ) input mellett. Ebb}ol (k=X 2);1 X t X 1 t js (x  y )s 1 jsk=2 (xj  yj )j + jPj  l j j k;l+1 (xj  yj )j: t j=1 t j =1

l=1 Az sk=2 (xj  yj ) bitsorozatok egy prex-mentes halmazt alkotnak, mint azt a 2.3 Lemmaban lattuk. Viszont a kozrefogasi (227) lemma miatt az sl (xj  yj )sk;l+1 (xj  yj ) bitsorozatok is mind kulonboznek, gy ezek is egy prex-mentes halmazt alkotnak. Ezert a 24 Lemma mind a k=2 darab atlagertekre alkalmazhato, amib}ol jPj  log t + (k=X 2);1 j =1 log t = (k=2) log t: Ha k paratlan, akkor k=2 helyett mindenhol dk=2e irando.  2.29 TE TEL: Ha f -re letezik ketszerepl}os protokoll t lehetseges kommunikacios bitsorozattal, akkor C (f )  2 log 32 t Bizonytas: A feltetel azt jelenti, hogy letezik f -re ketszerepl}os protokoll, melyhez tartozo protokoll fanak t levele van. Elkepzelhet}o azonban, hogy e protokoll fanak nagy a melysege. A C (f ) fels}o becslesehez e fabol egy kiegyensulyozottabb faval rendelkez}o protokollt konstrualunk, melynek melysege legfeljebb 2 log 23 t , ami biztostja tetel alltasat. Egy t level}u binaris

faban letezik olyan v pont, hogy tv -a v gyoker}u reszfa leveinek szamateljesti a t=3 < tv  2t=3 feltetelt. Ilyet talalhatunk, ha elindulunk a gyokerb}ol, es mindig abba az iranyba megyunk, amelyik gyerekhez tartozo reszfanak tobb, mint 2t=3 levele van. Amikor ezt mar nem tudjuk megtenni, akkor egy olyan pontban vagyunk, melynek egyik gyereke megfelel v-nek. Jelolje Rv azon (x y) inputparok halmazat X  Y -bol, melyek eljutnak a v pontba. Tekintsuk a kovetkez}o uj protokollt f -re: Els}okent A es B jatekosok eldontik, hogy a kapott (x y) inputpar Rv -ben ven-e. Ehhez 2 bit kommunikaciora van szukseg. (1.) Amennyiben (x y) 2 Rv , akkor az eredeti protokollt a v pontbol folytatjak azaz az Rv -re megszortott f -re, melyre tehat egy tv level}u protokoll fa all rendelkezesre. (2.) Ha (x y) 62 Rv , akkor akkor az eredeti protokollt hasznaljak az f  : X  Y ;! f0 1g fuggvenyre, ahol f  = f az Rv -n kvul, es f  = 0 az Rv -n. Az f

-re vonatkozo protokoll fajaban a v gyoker}u reszfat egy 0-val helyettestve egy t ; tv + 1 level}u protokoll fat kapunk f  -ra. Nem okoz gondot, hogy a 2 esetben f helyett f  -ot szamoljak a jatekosok, ugyanis ha (x y) 2 Rv , akkor nem is ezt az estet alkalmazzuk. A v megvalasztasa miatt mindket esetre kaptunk egy-egy protokollt nem tobb, mint 2t=3 levellel. Ha D(t)-vel jeloljuk, hogy egy t level}u protokollbol ezen algoritmus ismetelgetesevel mekkora melyseg}u protokollhoz lehet biztosan eljutni, akkor D(t)  2 + D(2t=3) kell teljesuljon. Mivel D(1) = 0, gy a rekurzv kepletb}ol D(t)  2 log 32 t kovetkezik  Most mar keszen allunk, hogy kimondjuk a kvant tetelt: 18 2.30 TE TEL: Letezik konstans, hogy minden f , k mellett fennall Ck (f )  k C (f ): Bizonytas: A 2.28 Lemmabol f -re letezik ketszerepl}os protokoll, melyhez tartozo protokoll fanak legfeljebb 2Ck(f )=dk=2e levele van. Alkalmazva a 229 Tetelt a C (f )  2

log3=2 (2Ck(f )=dk=2e ) eredmenyre jutunk, amit atalaktva kapjuk, hogy Ck (f )  21 log 23 dk=2e C (f ) > k C (f )  ahol > 0 146.  2.31 MEGJEGYZE S: E Kushilevitz ramutatott, hogy a 229 Tetelbeli becsles javtasaval akar C (f )  1 813 : : : log t is elerhet}o, amib}ol egy er}osebb, Ck (f )  0 275 k C (f ) becslest kapunk. 19 3. A ,,homlokra ragasztott szam" modell A modell Ebben a modellben, melyet 1] reszletesen targyal k jatekos vesz reszt. Mindegyikuk sajat inputtal rendelkezik, a kommunikacio pedig tablas, azaz egy elhangzott bitr}ol minden jatekos tudomast szerez. Van meg egy igen specialis tulajdonsaga is ennek a modellnek, megpedig az, hogy a szerepl}ok inputjai kozott nagy (s}ot a lehet}o legnagyobb) az atfedes. A legjobban ugy fogalmazhatunk, hogy a szerepl}ok mindegyike nem egy-egy inputtal rendelkezik, hanem eppenhogy egy-egy inputtal nem rendelkezik. Azaz minden szerepl}o birtokaban van a k darab

inputreszb}ol (k ; 1) , es persze mindegyikukt}ol masik inputresz hianyzik. A modell az elnevezeset is e specialis tulajdonsagarol kapta, hiszen ugy kepzelhetjuk el a jatekosokat, mintha egy asztal korul ulve mindegyikuknek egy-egy szam lenne ragasztva a homlokara, gy valamennyi jatekos latna az osszes szamot, kiveve a sajat homlokan lev}ot. Pontosabban megfogalmazva tehat a P1  P2 : : : Pk szerepl}ok kvanjak egy adott f : (f0 1gn )k ;! f0 1g fuggveny f (x1  x2  : : :  xk ) erteket kiszamtani ugy, hogy a Pi jatekos inputja (x1  x2  : : :  xi;1  xi+1 : : : xk ) , ahol tehat az xj -k n hosszu 0/1-sorozatok, azaz xj 2 f0 1gn : j = 1 2 : : :  k. Ehhez rendelkeznek egy P protokollal, mely megmondja hogy adott pillanatban veget ert-e a kommunikacios folyamat (ez esetben mi az eredmeny), es ha nem, akkor melyik jatekos kovetkezik szolasra, ez (az egyszerre beszeles kizarasa erdekeben) csak a tabla addigi

tartalmatol fugg. Megmondja tovabba, hogy a soron kovetkez}o jatekos sajat inputjanak, es a tabla addigi tartalmanak fuggvenyeben milyen bitet rjon fel a tablara A kommunikacio hossza a tablara felrt bitek szama. Szokasos modon a protokoll hossza, a kulonboz}o inputok mellett a leghosszabb el}ofordulo kommunikacio hossza, es egy fuggveny kommunikacios komplexitasa - melyet e modellben jeloljon C k (f ) - pedig a fuggvenyt szamolo lehet}o legrovidebb protokoll hossza. Cilinder metszetek E modell legnagyobb el}onye, hogy a protokoll fa nagyon hasonloan viselkedik, mint a ketszerepl}os esetben. Emlekezzunk vissza, hogy ott egy olyan binaris farol volt szo, melynek csucsait A es B betukkel jeloltuk meg, aszerint, hogy ki kovetkezett szolasra, es a csucsokbol az elkuldott bit alapjan haladtunk tovabb a ket lehetseges gyerek valamelyikebe. A kulonbseg itt csak az, hogy a protokoll fa csucsainak k lehetseges

megjelolese lehet, hisz k jatekos kovetkezhet szolasra. Ebben a "homlokra ragasztott szam" modellben egy, az 1.4 Tetellel teljesen analog tetel igaz, azzal a kulonbseggel, hogy az ottani reszmatrixoknak itt cilinder-metszetek felelnek meg. 3.1 DEFINICIO : Az Si  X1  X2   Xk halmaz cilinder halmaz az i-edik dimenzioban, ha az Si-beliseg, mint tulajdonsag nem fugg az i-edik koordinatatol, azaz (x1  : : :  xi;1  xi  xi+1 : : :  xk ) 2 Si () (x1  : : :  xi;1  xi  xi+1 : : :  xk ) 2 Si 8xj 2 Xj (j = 1 : : :  k )  8xi 2 Xi 20 3.2 Tk DEFINICIO : Az S  X1  X2   Xk halmaz cilinder-metszet, ha el}oall S = i=1 Si alakban, ahol Si halmaz rendre cilinder az i-edik dimenzioban. A jobb szemleltetes erdekeben is hasznos megadni a cilinder-metszetek egy masik, ekvivalens denciojat, amit a szemleltetesen tul sok helyen tudunk majd kvaloan alkalmazni. 3.3 DEFINICIO : Egy pont k-ast csillagnak nevezunk X1  X2  

Xk -ban, ha a kovetkez}o alaku: (x1  x2  : : :  xk )  (x1  x2  : : :  xk )  : : :  (x1  x2  : : :  xk ) ahol xi  xi 2 Xi , es xi 6= xi 8i 2 f1 : : :  kg. A fenti csillag kozeppontja (x1  x2  : : :  xk ) 3.4 TE TEL: S cilinder-metszet () minden C  S csillag kozeppontja Tk is S -ben van. Bizonytas: (=)) Tegyuk fel, hogy S cilinder-metszet az S = i=1 Si el}oalltassal, es C = f(x1  x2  : : :  xk )  (x1  x2  : : :  xk )  : : :  (x1  x2  : : :  xk )g egy csillag S -ben. Akkor minden i mellett teljesul (x1  : : :  xi  : : :  xk ) 2 S  Si =) (x1  : : :  xi  : : :  xk ) 2 Si , hiszen Si cilinder az i-edik dimenzioban. Mivel (x1  : : :  xi  : : :  xk ) 2 Si 8i = 1 2 : : :  k ebb}ol (x1  : : :  xi  : : :  xk ) 2 S , tehat a csillag kozeppontja is S -ben van. ((=) Legyen az S olyan, hogy minden S -beli csillag kozeppontja is S -ben van. Az Si := f(x1  : : :  xi  : : :  xk ) 2 X1 X2  Xk j 9xi 2 Xi : (x1  :

: :  xi  : : :  xk ) 2 S g jeloles mellett (i = 1 2 : : :  k) nyilvanval o, hogy Si halmaz cilinder az i-edik dimenzioban. Meg T k kell m Tekg mutatnunk, hogy Tk S = i=1 Si : Az Si-k denciojabol vilagos, hogy S  Si 8i =) S  i=1 Si : Az S  Ti=1 Si iranyu tartalmazas pedig abbol kovetkezik, hogy amennyiben (x1  : : :  xi  : : :  xk ) 2 ki=1 Si , akkor 8i-re 9xi , hogy (x1  : : :  xi  : : :  xk ) 2 S : Ezek az S beli elemek egy csillagot alkotnak, melynek kozeppontja, azaz (x1  : : :  xi  : : :  xk ) a feltetel szerint ugyancsak S -ben kell legyen.  Jeloljuk R`-lel azon inputok halmazat az X1  X2   Xk -bol, melyek mellett az ` levelbe jutunk a protokoll faban. 3.5 TE TEL: A protokoll fa mindel ` levelere az R` halmaz egy monokromatikus cilinder-metszet. Bizonytas: Hogy R` monokromatikus, az nyilvanvalo. Az 14 Tetel bizonytasahoz hasonloan teljes indukcioval megmutathato, hogy a protokoll fa minden v pontjara az inputok

azon Rv halmaza, melyek elerik a v pontot cilinder-metszetet alkotnak. Azonban a 3.4 Tetel altal adott ekvivalens denciot hasznalva a cilinder-metszetre egy megegyszer}ubb bizonytast adhatunk: Megmutatjuk, hogy minden R`-beli csillag kozeppontja is ott van. Ez igaz hiszen ha  (x1  x2  : : :  xk )  (x1  x2  : : :  xk )  : : :  (x1  x2  : : :  xk ) 2 R` , akkor ezen inputok mind az ` levelbe vezetnek. Viszont amikor Pi jatekos (i = 1 2 : : :  k) mond egy bitet, akkor }o nem tud kulonbseget tenni az (x1  : : :  xi  : : :  xk ) es (x1  : : :  xi  : : :  xk ) inputok kozott, gy a kommunikacio az (x1  : : :  xi  : : :  xk ) input eseten is az ` levelbe jut.  3.6 KO VETKEZME NY: Egy t bit hosszusagu protokoll az X1  X2   Xk inputhalmazt legfeljebb 2t darab monokromatikus cilinder-metszetre osztja. 21 Becslesek diszkrepanciaval A ltalaban a ketszerepl}os kommunikacios komplexitasra vonatkozo also becslesek nem

m}ukodnek a tobbszerepl}os modellben. Az egyetlen modszer, amely egy az egyben atvihet}o az a diszkrepancia modszer. E modszer jol hasznalhato a ketszerepl}os modellben az "-hibas kommunikacios komplexitas, es ezaltal a kommunikacios komplexitas also becslesere is. 3.7 DEFINICIO : Azt mondjuk, hogy egy P protokoll " hibaval kiszamolja az f fuggvenyt a ketszerepl}os modellben (0  "  1=2), ha Pr(P (x y) = f (x y))  1 ; " , ahol P (x y)-nal azt az eredmenyt jeloljuk, amit a P protokoll szamol az (x y) inputra. A valoszn}useget itt ugy kell erteni, hogy a lehetseges (x y) 2 X  Y inputok egyenl}o valoszn}useggel lephetnek fel. Tehat a protokoll egy 1=2-nel nagyobb, de nem feltetlenul 1 valoszn}useggel adja a helyes eredmenyt egy (x y) veletlenszer}uen valasztott inputon. Jeloljuk C"(f )-fel a legrovidebb, f -et " hibaval szamolo protokoll hosszat. Megjegyzend}o, hogy eredetileg ezt a

jelolest olyan esetben alkalmazzak, amikor a protokoll veletlent (pl. penzfeldobasokat) is hasznalhat. A tetelek, melyeket igazolunk erre az esetre is igazak, de nincs szukseg e fejezetben a veletlen hasznalatara, gy a denciot e nelkul mondtuk ki. Ha M az Mf matrix egy reszmatrixa, akkor Disc(f M ) := jPrf (x y) = 0 (x y) 2 M ] ; Prf (x y) = 1 (x y) 2 M ]j ahol a valoszn}useget az inputok egyenletes eloszlasa mellett kell erteni. A diszkrepanciat a ketszerepl}os modellben egy adott f fuggvenyre a kovetkez}okeppen denialjuk: Disc(f ) := max Disc(f M ) M ahol M vegigfut az Mf osszes reszmatrixan. A diszkrepanciat termeszetesen nem csak egyenletes inputeloszlas mellett lehet ertelmezni, de itt nekunk csak arra lesz szuksegunk. 3.8 TE TEL: Minden f : X  Y ;! f0 1g fuggveny, es 0  "  1=2 mellett igaz, 2 " hogy C 12 ;"(f )  log Disc(f ) : Bizonytas: Amennyiben P egy t bitet hasznalo protokoll az f

-re, amely legalabb 1 + " valoszn}useggel ad helyes eredmenyt, akkor 2 2"  PrP (x y) = f (x y)] ; PrP (x y) 6= f (x y)] = X = (PrP (x y) = f (x y) es (x y) 2 R`] ; PrP (x y) 6= f (x y) es (x y) 2 R`]) ` ahol a szummazas a protokoll fa osszes levelere tortenik. Mivel az R` halmazok P -re nezve monokromatikusak, gy a kifejezes tovabb becsulhet}o felulr}ol azzal, hogy: X ` jPrf (x y ) = 0 es (x y ) 2 R` ] ; Prf (x y ) = 1 es (x y ) 2 R` ]j : 22 Mivel minden R` egy-egy reszmatrixa Mf -nek, gy a szumma minden egyes tagjat felulr}ol becsli a Disc(f ). A szummanak pedig legfeljebb 2t tagja lehet, hiszen legfeljebb ennyi levellel rendelkezhet egy t melyseg}u binaris fa. Tehat azt kaptuk, hogy 2"  2t Disc(f ) , 2" ) egyenl}otlenseg adodik.  amib}ol atrendezessel a kvant t  log ( Disc (f ) 3.9 KO VETKEZME NY: C (f )  log Disc1 (f ) Nezzuk hogyan vihet}o at ez a tetel a ,,homlokra ragasztott

szam" modellre. Ebben a tobbszerepl}os modellben a diszkrepanciat a kovetkez}okeppen denialhatjuk: 3.10 DEFINICIO : Ha f : X1  X2   Xk ;! f0 1g fuggveny, S pedig egy cilinder-metszet X1  X2   Xk -ben, akkor Disc(f S ) := jPrf (x1  x2  : : :  xk ) = 0 (x y) 2 S ] ; Prf (x1  x2  : : :  xk ) = 1 (x y) 2 S ]j Disc(f ) := max Disc(f S )  S ahol a maximumot az osszes cilinder-metszet felett vesszuk. A ketszerepl}os esettel analog modon denalhato k szerepl}o eseten az "-hibas kommunikacios komplexitas (C"k ), melyre akarcsak ott is igaz a kovetkez}o tetel. 3.11 TE TEL: C k12 ;"(f )  log Disc2"(f ) : Bizonytas: A 3.8 Tetel bizonytasa egy az egyben atvihet}o a tobbszerepl}os esetre 3.12 KO VETKEZME NY: C k(f )  log Disc1 (f ) E kovetkezmeny felhasznalasaval a diszkrepancia fels}o becslesevel a kommunikacios komplexitast alulrol tudjuk becsulni. Nezzuk ezt meg az altalanostott bels}o

szorzat (a GIP ) fuggveny eseteben. 3.13 DEFINICIO : Ha x1  x2  : : :  xk 2 f0 1gn, akkor az altalanostott bels}o szorzat fuggvenyt ugy denialjuk, hogy GIPnk (x1  x2  : : :  xk ) = 1 pontosan akkor, ha paratlan azon 1  j  n indexek szama, melyekre valamennyi xi j -edik bitje 1. E fuggveny kommunikacios komplexitasara el}oszor Babai, Nisan es Szegedy adott also becslest 5]-ben: 3.14 TE TEL: C k(GIPnk ) = ( 4nk ) Bizonytas: A 3.12 Kovetkezmeny ertelmeben eleg megmutatnunk, hogy n Disc(GIPnk )  e;( 4k ) : Az egyszer}ubb algebrai kezelhet}oseg erdekeben vezessuk be a kovetkez}o f fuggvenyt:  ha GIPnk (x1  : : :  xk ) = 0 f (x1  : : :  xk ) := +1 ;1 ha GIPnk (x1  : : :  xk ) = 1 Jelolje "k (n) =  max jE f (x1  : : :  xk ) 1(x1  : : :  xk ) k (x1  : : :  xk )]j  ::: x1:::xk 1 k 23 ahol a maximumot az osszes olyan 1 : : :  k fuggvenysorozat felett vesszuk, ahol k n i : (f0 1g ) ;! f0 1g fuggveny

nem fugg az xi valtozotol, az Ex1 :::xk pedig varhato erteket jelol az inputok egyenl}o valoszneggel torten}o valasztasa mellett. Vegyuk eszre, hogy Disc(GIPnk ) = "k (n), ugyanis azon pontok halmaza az X1   Xk inputterb}ol, melyekre 1(x1  : : :  xk ) k (x1  : : :  xk ) ertek 1-et ad egy cilinder metszetet alkot, es minden cilinder-metszet felrhato egy ilyen szorzattal. Tovabba mivel attertunk a f;1 +1g ertekekre, ezert itt a varhato ertek megegyezik a valoszn}usegek kulonbsegevel a diszkrepancia denciojaban. q 1+ j;1 Denialjuk rekurzv modon a kovetkez}o szamsorozatot: 1 := 0, es j := 2 . Indukcioval konnyen kijon, hogy k  1 ; 41;k < e;41;k , ezert azt kell igazolnunk, hogy "k (n)  ( k )n : Ezt k-ra vonatkozo teljes indukcioval fogjuk megtenni. Nyilvan "1(n) = 0 = 1 , hiszen ekkor 1 konstans, ezaltal "1(n) = Ex1 f (x1 )] = 0 . Tegyuk fel, hogy k  2, es k-nal kisebb ertekekre

tudjuk, hogy igaz az alltas. Legyenek 1 : : :  k olyan fuggvenyek, melyek mellet "k (n) felveszi az erteket. Mivel k fuggveny nem fugg az xk valtozotol, es abszolut erteket felulr}ol becsulhetjuk 1-gyel, gy "k (n)  Ex1:::xk;1 jExk f (x1  : : :  xk ) 1(x1  : : :  xk ) k;1(x1  : : :  xk )]j] : Felhasznalva a Cauchy-Schwartz egyenl}otlenseg egy speciacialis esetet, azaz, hogy egy z valoszn}usegi valtozora (E z])2  E z2] azt kapjuk, hogy "k (n)  (Ex1:::xk;1 Exk f (x1  : : :  xk ) 1(x1  : : :  xk ) 1=2 2 k;1 (x1  : : :  xk )]] ) = 1=2 u v = (Euvx1:::xk;1 f (x1  : : :  xk;1  u) f (x1  : : :  xk;1  v) u1 v1 k;1 k;1 ])  ahol ui = i(x1  : : :  xk;1  u) es vi = i(x1  : : :  xk;1  v) . Az xi 2 f0 1gn vektorokat tekinthetjuk egy n elem}u X halmaz egy-egy reszhalmazanak a karakterisztikus vektoranak, azaz az xi vektort azonosthatjuk Tk xaj neki megfelel}o j reszhalmazzal. Vegyuk eszre,

hogy ekkor f (x1  : : :  xk ) = (;1) i=1 i , ahol a jobb oldalon lev}o xi -k mar mint halmazok ertend}ok. Ebb}ol u4v-vel jelolve az u es v halmazok szimmetrikus dierenciajat az adodik, hogy Tk;1 Tk;1 f (x1  : : :  xk;1  u) f (x1  : : :  xk;1  v) = (;1)ju i=1 xij+jv i=1 xi j = Tk;1 T = (;1)j(u4v) i=1 xi j = (;1) zi = f (z1  : : :  zk;1 ) ahol zi = xi (u4v) , azaz minden xi vektor ket reszre, yi -re es zi -re oszthato, ahol zi az xi azon j -edik koordinataibol all, amelyekre uj 6= vj . Itt kihasznaltuk, hogy azon elemek, melyek u-ban es v-ben (mint reszhalmazban) egyarant benne vannak, illetve amelyek egyikben sincsenek benne, azok a (;1) kitev}ojeben paros sokszor szerepelnek, gy nyugodtan elhagyhatok. Akkor tehat u v ]])1=2 : "k (n)  (Euvy1:::yk;1 Ez1:::zk;1 f (z1  : : :  zk;1 ) u1 v1 k;1 k;1 24 A zi -k, mint lattuk ju4vj hosszu vektorok, a ui vi szorzatfuggveny pedig tekinthet}o a (z1  z2 : : :  zk;1 ) valtozokon

ertelmezett fuggvenynek, amely viszont nem fugg a zi valtozotol, gy az indukcios felteves miatt Ez1:::zk;1 f (z1  : : :  zk;1 ) u v 1 1 u v ]  "k;1 (ju4v j)  ( k;1 )ju4vj k;1 k;1 : Tehat azt kaptuk, hogy "k (n)  (Euvy1:::yk;1  kju;41vj])1=2 = (Euv  kju;41vj])1=2 : Amennyiben u es v uniform modon valasztott veletlen vektorok a f0 1gn-b}ol, ;akkor  ;naz n u 4 v vektor (illetve halmaz) eloszlasa is egyenletes, tehat Pr(ju4vj = m) = m 2 . Ezert a becsles gy folytathato tovabb: n n X "k (n)   2;n m m=0 n m 1=2 ;n n 1=2 k;1 ] = 2 (1 + k;1 ) ] = ( k ) : 3.15 MEGJEGYZE S: Ez a becsl es tovabb javthato, ugyanis, mint azt Chung es n Tetali 8]-ban megmutatta GIPnk = ( 2k ). Bizonytasuk a kvazi-random grafok elmeleten alapul. Ebben a modellben valamennyi ismert also becsles, akarcsak ez is a k novelesevel exponencialisan csokken. Jo lenne olyan fuggvenyt talalni, melyre k-tol legalabb nem

exponencialisan fugg}o, peldaul knc tpusu also becsles adhato Az el}obb latott GIP fuggveny biztosan nem ilyen, ugyanis Grolmusz Vince 10]-ben igazolta, hogy az 2nk also becsles mar eles. 3.16 TE TEL: GIPnk = O(k 2nk ) Bizonytas: Celszer}u az inputokat egy k n-es A matrixkent tekinteni, melynek tehat i-edik sora az xi inputresz. A GIPnk fuggveny az A matrix csupa 1-esekb}ol allo oszlopai szamanak paritasat adja meg. Tekintsuk a kovetkez}o protokollt ennek kiszamtasara Bontsuk fel az A matrixot 2k;1 ; 1 oszlopbol allo blokkokra, persze az utolso blokkba a maradek oszlopok kerulnek, melyek szama lehet ennel kisebb. Vegyuk eszre, hogy ha a GIPnk erteket ezekre a blokkokra kiszamtjuk , akkor ezeket az ertekeket mar csak osszegezni kell modulo 2. Nezzuk, hogyan szamolhatjuk ki egy adott blokkra a GIPnk erteket nem tobb, mint 2k bit kommunikacioval: El}oszor P1, az els}o jatekos kijelent egy olyan  vektort, amely

nem szerepel az adott blokk oszlopai kozott. Ugyan nem ismeri az els}o sort, megis tud ilyet mondani, hiszen a legfeljebb 2k;1 ; 1 oszlop mindegyikenek csak az els}o koordinatajat nem ismeri, gy azok helyere mindket lehetseges bitet berva is csak 2k ; 2 oszlop johet szamtasba, viszont osszesen 2k fele oszlopvektor letezik. Amennyiben  = (1 1 : : :  1) , akkor e blokkra a GIPnk erteke biztosan 0, es nincs is szukseg tovabbi kommunikaciora. Ha nem, akkor az  vektornak letezik 0 koordinataja Feltehetjuk, hogy  = (0 : : :  0 1 : : :  1) alaku, ahol l darab 0 utan k ; l darab 1-es kovetkezik, ugyanis ellenkez}o esetben a jatekosok atpermutalhatok ugy, hogy ilyen alakuva 25 valjon. Jelolje yi (i = 0 1 2 : : :  k) a blokkban szerepl}o (0 : : :  0 1 : : :  1) alaku oszlopok szamat mod 2, ahol i darab 0 utan jon k ; i darab 1-es, zi pedig (i = 1 2 : : :  k) a blokkban szerepl}o (0 : : :  0  1 : : :  1) alaku

oszlopok szamat mod 2, ahol i ; 1 darab 0-t egy tetsz}oleges bit kovet az i-edik pozcioban, majd n ; i darab 1-es kovetkezik. Most minden i-re Pi bejelenti a zi erteket, amit nyilvan meg tud allaptani a sajat inputjabol. Mivel zi = yi + yi;1 , es yl = 0 ismert, mert  nem fordul el}o az oszlopok kozott, gy a zi-kb}ol kiszamthato y0 , ami nem mas, mint a GIPnk -nak erre a blokkra megszortott erteke. Meghozza y0 = y0 + yl = l M i=1 zi : (A  mod 2 osszeadast jelent.) Az  bejelentese k bitet igenyel, mg a zi-k kozlese tovabbi k bit. Mivel a blokkok szama O( 2nk ), es minden blokkra eleg 2k bit kommunikacio,gy e protokoll valoban O(k 2nk ) kommunikacioval szamolja GIPnk erteket.  A kocka-modszer Ez a modszer valojaban meg a diszkrepanciat hasznalo also becslesi modszerek koze tartozik. Ran Raz 9] felfedezett egy olyan, fuggvenyekhez rendelhet}o mennyiseget, amely a diszkrepanciat felulr}ol becsli, viszont

kiszamtasa sokkal egyszer}ubb. Tulajdonkeppen a 3.14 Tetel bizonytasanak egy altalanostasarol van szo, melyet ha elvegzunk, akkor sok fuggvenyre a szamolas jelent}osen csokkenthet}o. 3.17 DEFINICIO : Az X = X1  X2   Xk inputterben kockanak nevezunk egy D = fa1 b1 g  fa2  b2g   fak  bk g alaku reszhalmazt, ahol 8i : ai  bi 2 Xi (nem feltetlenul kulonboz}oek). Jelolje D az osszes kockak halmazat 3.18 DEFINICIO : Egy D 2 D kocka (f -re vonatkozo) el}ojele legyen Sf (D) := Y Y Y d1 2fa1 b1 g d2 2fa2 b2 g dk 2fak bk g f (d1  : : :  dk ) ahol az f a f;1 +1g-be kepez}o fuggveny. A f0 1g-be kepez}o Boole-fuggvenyeket ezert el}obb at kell alaktani ilyenne, mint azt a 3.14 Tetel bizonytasaban is tettuk Lathato, hogy az Sf : D ;! f;1 +1g fuggveny pontosan akkor ad +1 erteket, amennyiben a D kockan az f paros sok helyen vesz fel ;1-et (es ekkor 1-et is). 3.19 DEFINICIO : Jelolje E (f ) := ED Sf

(D)], ahol a varhato erteket a D uniform megvalasztasa mellet tekitjuk (ez persze ekvivalens azzal, hogy az ai  bi elemeket uniform modon valasztjuk az Xi -b}ol minden i = 1 2 : : :  k mellett). Ennek az E (f )-nek az 21k -adik hatvanya lesz az a mennyiseg, ami felulr}ol becsli a diszkrepanciat. Ezt majd a 322 Tetelben fogjuk latni 3.20 LEMMA: Jelolje egy h : X ;! f;1 +1g fuggvenyre "(h) := Ex2X h(x)], ahol a varhato erteket az egyenletes eloszlas szerint vesszuk. Akkor k E (h)  j"(h)j2 : 26 Bizonytas: E (h) = ED Sh (D)] = Ea1 b1 2X1 Eakbk2Xk Y Y d1 2fa1 b1 g dk 2fak bk g h(d1  : : :  dk ): Tetsz}oleges Xk -n ertelmezett g fuggvenyre fennall Eakbk2Xk g(ak )g(bk )] = (Exk2Xk g(xk )])2 : Rogztett a1  b1  : : :  ak;1  bk;1 mellett legyen most g(xk ) = Y Y d1 2fa1 b1 g dk;1 2fak;1 bk;1 g Ezaltal E (h) = Ea1b1 2X1 Y Y d1 2fa1 b1 g dk;1 2fak;1 bk;1 g ; Eak;1bk;12Xk;1 Exk h(d1 : : :  dk;1 

xk ):  h(d1 : : :  dk;1 xk ) 2: Alkalmazva a Cauchy-Schwartz egyenl}otlenseget, mely szerint egy z valoszn}usegi valtozora E z2]  (E z])2 , az kovetkezik, hogy E (h)  (Ea1 b12X1 ; = Exk Ea1b12X1 Eak;1bk;12Xk;1 Exk Eak;1bk;12Xk;1 Y Y d1 2fa1 b1g dk;1 2fak;1 bk;1 g Y d1 2fa1 b1g Ezt k-szor ismetelve pedig azt kapjuk, hogy E (h)  (Exk 2Xk Y dk;1 2fak;1 bk;1 g  h(d1  : : :  dk;1  xk ) 2  h(d1  : : :  dk;1  xk ) 2 : Ex12X1 h(x1  : : :  xk ))2k = j"(h)j2k : 3.21 LEMMA: Tetsz}oleges f : X ;! f;1 +1g fuggvenyhez letezik egy olyan  h : X ;! f;1 +1g fuggveny, amelyre E (h) = E (f ), es j"(h)j  Disc(f ). Bizonytas: Azt fogjuk hasznalni, hogy amennyiben tetsz}oleges i 2 f1 2 : : :  kg mellett g nem fugg az i-edik valtozojatol, akkor E (fg) = E (f ) (itt fg(x) = f (x)g(x) a szorzatfuggvenyt jeloli). Ez 8 f g mellett igaz, hiszen nyilvan minden D kockara a dencio szerint Sfg (D) = Sf (D)Sg (D), es ha g

nem fugg peldaul az xk valtozotol, akkor g(d1 : : :  dk;1 ak ) = g(d1 : : :  dk;1 bk ) 8d1 : : :  dk  ak  bk mellett, gy a g fuggveny paros sok D-beli elemen ad 1-et, tehat Sg (D) = 1. Ebb}ol az is kovetkezik, hogy ha gi nem fugg az i-edik valtozojatol, akkor E (fg1 g2 gk ) = E (f ): T Jeloljon most T = ki=1 Ti egy olyan cilinder-metszetet, melyre Disc(f T ) = Disc(f ). Legyen i 2 f1 2 : : :  kg eseten gi : X ;! f;1 +1g a kovetkez}o fuggveny (valoszn}usegi 27 valtozo): gi(x) = 1 (1 valoszn}useggel) ha x 2 Ti , ellenkez}o esetben pedig 21 valoszn}useggel gi(x) = 1 illetve 12 valoszn}useggel gi(x) = ;1. A gi-k legyenek persze fuggetlenek Jelolje tovabba g := g1g2 gk . Akkor az el}obb emltettek miatt teljesul E (fg ) = E (f ): Vegyuk eszre, hogy amennyiben x 2 T , akkor (1 valoszn}useggel) g(x) = 1, kulonben pedig 21 valoszn}useggel g(x) = 1, es 12 valoszn}useggel g(x) = ;1. Ezert ha x 2 T ,

akkor Eg g(x)] = 1 ha pedig x 62 T , akkor Eg g(x)] = 0. Azaz Eg eppen a T halmaz karakterisztikus fuggvenye. Ezaltal jEg "(fg )j = jEg Ex f (x )g (x)]j = jExEg f (x )g (x)]j = jExf (x )Eg g (x)]]j = = jjfx : x 2 T f (x) = 1gj ; jfx : x 2 T f (x = ;1)gjj = Disc(f T ): A konvexitas miatt pedig Eg j"(fg)j  jEg "(fg)j = Disc(f T ) = Disc(f ): Tehat letezik olyan g, hogy a h = fg valasztas mellett teljesulnek a kvant feltetelek. 3.22 TE TEL: 8f : X ;! f;1 +1g fuggvenyre E (f )  Disc(f )2k Bizonytas: A 3.21 Lemmabol nyert h-ra alkalmazva a 320 Lemmat k k E (f ) = E (h)  j"(h)j2  Disc(f )2 : 3.23 KO VETKEZME NY: C k(f )  2;k log E (1f ) : Bizonytas: A 3.12 Kovetkezmeny es a 322 Tetel kovetkezmenye Hogy eddig eljussunk sokat kellett szamolnunk, de megerte, ugyanis sok f -re az E (f ) pontos erteke konnyen, kombinatorikai eszkozokkel szamolhato. Nezzuk meg peldaul a GIP fuggvenyhez

tartozo E erteket. 3.24 A LLITA S: E (f ) = (1 ; 2k1;1 )n , ahol f a GIPnk fuggveny f;1 +1g ertekkeszlet}u valtozata. Bizonytas: Legyen D = fa1 b1 g  fa2  b2g   fak  bk g egy tetsz}oleges kocka (f0 1gn)k -ban. Mint azt a 314 Tetel bizonytasaban mar lattuk, ez a fuggveny tulajdonkeppen egy n elem}u alaphalmaz reszhalmazaira megadja a metszet paritasat Jeloljuk ezert a kisbet}us 0=1 sorozatoknak megfeleltethet}o reszhalmazt a megfelel}o nagybet}uvel. Akkor Sf (D) = Y d 2fai bi g i2fi 12:::k g Ebb}ol pedig f (d1  : : :  dk ) = T j k Y Di 2fAi Bi g i2f12:::kg (;1) Tk Sf (D) = (;1)j 28 i=1 Di j i=1 Ai 4Bi j  = (;1) P Tk Di 2fAi Bi g j i=1 Di j i2f12:::kg : hiszen azon elemek, melyek nem Ai 4 Bi-ben vannak biztosan paros sokszor adodnak ossze a (;1) kitev}ojeben. A D kocka veletlen megvalasztasa ekvivalens az Ai  Bi halmazok uniform modon torten}o megvalasztasaval. Ekkor pedig az Ai 4 Bi halmaz is az

egyenletes eloszlas szerint valasztodik ki, azaz minden alaphalmazbeli elem 1=2 valoszn}useggel van Ai 4 Bi -ben. Ebb}ol n X E (f ) = ED Sf (D)] = (;1)j pj  j =1 ahol pj annak a valoszn}usege, hogy az n elem}u alaphalmaz k darab veletlenszer}uen valasztott reszhalmazanak metszete j elem}u. Tehat n 1 j  1 n;j pj = j 2k 1 ; 2k E s gy E (f ) = n X j =1 (;1)j n 1 j  1 n;j  1  1 n  1 n:  1 ; = 1 ; ; = 1 ; 2k 2k 2k 2k;1 j 2k Ebb}ol pedig a 3.23 Kovetkezmennyel ismet adodik a 314 Tetel Nezzunk meg a kocka modszert egy masik fuggveny eseten is. Jelolje X = f0 1gnn az n  n-es 0=1 matrixok halmazat. Ha x1  x2  : : :  xk 2 X , akkor az F , matrix szorzas fuggvenyt a kovetkez}okeppen ertelmezzuk: F (x1  x2  : : :  xk ) = (x1 x2 xk )11 : Tehat F (x1  x2  : : :  xk ) az x1 x2  : : :  xk matrixok (GF (2) felett tekintett) szorzatanak bal fels}o sarkaban lev}o eleme. Terjunk at ismet f;1 +1g

ertekkeszletre, azaz legyen f (x1  x2  : : :  xk ) := (;1)F (x1 x2:::xk). 3.25 A LLITA S: Erre az f -re E (f )  k2;n1 Bizonytas: Legyen D = fa1 b1 g  fa2  b2g   fak  bk g egy tetsz}oleges kocka k X -ban. Akkor Sf (D) = Y di 2fai bi g i2f 12:::kg f (d1  : : :  dk ) = P Y di 2fai bi g i2f 12:::kg (;1)F (d1 d2:::dk) = (;1) di 2fai bi g F (d1 d2 :::dk ) i2f 12:::kg Az utobbi osszegzes nyilvan eleg, ha GF (2) felett tortenik. Mivel F minden valtozojaban linearis, gy ha  jeloli a GF (2) feletti osszeadast, akkor Sf (D) = (;1)F (a1 29 b1 a2 b2 :::ak bk ) Ha a D kocka uniform modon valasztott, akkor (a1  b1  a2  b2 : : :  ak  bk ) is egyenletes eloszlassal van valasztva X k -bol, ezert E (f ) = ED Sf (D)] = ED (;1)F (a1 b1 a2 b2 :::ak bk ) ] = = E~x(;1)F (x1 x2:::xk)] = E~xf (x1  x2  : : :  xk )] =: "(f ) A "(f ) becslesehez legyen (x1  x2  : : :  xk ) veletlen vektor

egyenletes eloszlassal veve az X k -bol. Jelolje Ed (1  d  k eseten) azt az esemenyt, hogy az x1 x2 xd matrix els}o soranak minden eleme 0. Legyen ezek utan pd := Pr(Ed ) Akkor p1 = Pr(E1 ) = 21n , valamint Pr(Ed+1 jEd) = 1, es mivel xd+1 is egyenletes eloszlasu, gy Pr(Ed+1j:Ed) = 21n . Ebb}ol ha 1  d < k, ugy pd+1 = pd + (1 ; pd ) 21n  pd + 21n  ami d-re vonatkozo indukcioval adja, hogy pd  d 21n : Amennyiben Ek;1 fennall, ugy f (x1  x2  : : :  xk ) biztosan 1, ellenkez}o esetben pedig mivel xk is egyenletes eloszlasu, ezert f (x1  x2  : : :  xk ) ekkor egyenl}o valoszn}useggel lehet +1 illetve ;1, azaz E (f ) = "(f ) = pk;1  (k ; 1) 1n  2 Ezzel az alltassal a 3.23 Kovetkezmeny segtsegevel megkaptuk, hogy a matrix szorzas fuggvenyere a ,,homlokra ragasztott szam" modellben C k (f ) = ( 2nk ). Raz egyebkent azt sejti, hogy ez az also becsles egyaltalan nem eles, gy a matrixszorzas fuggvenye egyike azon

fuggvenyeknek, melyekre varhato, hogy egy k-ban nem exponencialisan csokken}o also becslest lehet igazolni. Ramsey tpusu becslesek Id}onkent Ramsey tpusu szamokkal is lehet becsulni e modellben a kommunikacios komplexitast. A most kovetkez}o fuggvenyre mindket iranyu becslest e modszerrel adjuk meg.  : Jelolje ENk : f1 : : :  N gk ;! f0 1g azt a fuggvenyt, amelyre 3.26 DEFINICIO P ENk (x1  : : :  xk ) = 1 , ki=1 xi = N . Ez az un ,,pontosan N" fuggveny 3.27 DEFINICIO : Denialjuk a k (N ) Ramsey szamot a kovetkez}okeppen: k (N ) az a legkisebb termeszetes szam, melyre k (N ) sznnel ki lehet sznezni az f1 2 : : :  N gk;1 halmazt u gy, hogy minden (x1  : : :  xk;1 ) es minden  6= 0 mellet ha (x1 +  x2  : : :  xk;1 ) (x1  x2 +  : : :  xk;1 ) . . (x1  x2  : : :  xk;1 + ) (x1  x2  : : :  xk;1 ) 30 vektorok mind f1 2 : : :  N gk;1 -b}ol valok, akkor nem mind egyforma sznnel van sznezve. Egy ilyen

sznezest a tovabbiakban legalisnak mondunk. 3.28 TE TEL: C k(ENk ) = O(k + log k (N )) Bizonytas: Sznezzuk ki f1 2 : : :  N gk;1 -et k (N ) sznnel legalisan, es tekintsuk a kovetkez}o protokollt ENk kiszamtasara: P Minden i  k ; 1 -re a Pi jatekos szamolja ki az xi := N ; j6=i xj erteket. Megteheti, hisz xi kivetelevel minden inputot ismer. Az xi az az ertek, amennyinek az xi -nek kell lennie, hogy az ENk fuggveny 1-et adjon. Amennyiben 9i : xi  0, akkor biztos, hogy a szumma nagyobb N-nel, gy Pi mar tudja is, hogy a vegeredmeny 0. Egyebkent az el}obbi Pi -k szamoljak ki az (x1  : : :  xi  : : :  xk;1 ) sznet. A Pk jatekos szamolja az (x1  : : :  xk ) sznet. Ezek utan a jatekosok ellen}orzik, hogy valamennyi szn megegyezik-e Ha igen, az eredmeny 1, ha nem, az eredmeny 0. Vegyuk eszre, hogy ehhez eleg az els}o jatekosnak felrnia a szamolt sznt (log k (N ) bit), a tobbieknek pedig csak egy-egy bitet

kell kuldeni aszerint, hogy az }o sznuk megegyezik-e azzal. P Az gy szamolt eredmeny azert helyes, mert amennyiben kj=1 xj = N , akkor minden P i-re xi = xi , gy ekkor mindenki az (x1  : : :  xk ) sznet szamolja, mg ha kj=1 xj 6= N , P akkor kj=1 xj = N ; , gy ekkor a jatekosok altal szamolt sznek az (x1 +  x2  : : :  xk;1 ) (x1  x2 +  : : :  xk;1 ) . . (x1  x2  : : :  xk;1 + ) (x1  x2  : : :  xk;1 ) vektorok sznei. Mivel legalis sznezest vettuk, ezert ezek a sznek nem mind egyformak  3.29 TE TEL: C k(ENk )  log k (b Nk;;11 c) Bizonytas: Tehat azt kell belatnunk, hogy 2Ck (ENk )  k (b Nk;;11 c). Tekintsunk egy optimalis protokollt ENk -ra, akkor az ehhez tartozo protokoll fa melysege C k (ENk ), ezert leveleinek szama legfeljebb 2Ck (ENk ). Azonostsuk a kulonboz}o leveleket egy-egy kulonboz}o sznnel, gy azt kell megmutatni, hogy ezekkel a sznekkel meg lehet az f1 : : :  b Nk;;11 cgk;1 elemeit

legalisan sznezni. A sznezest ugy vegezzuk, P hogy az (x1  : : :  xk;1 ) vektor azt a levelet kapja szneul, ;1 x ) input mellett a protokoll fa visz. Mivel az x -k amelybe az (x1  : : :  xk;1  N ; ki=1 i i f1 : : :  b Nk;;11 cg-b}ol vannak, gy ez ertelmes, azaz a k -adik komponens is 1 : : :  N -be esik. Az gy megadott sznezes legalis, ugyanis ha van k egyszn}u vektor az f1 : : :  b Nk;;11 cg-b}ol a kovetkez}o alakban: (x1 +  x2  : : :  xk;1 ) (x1  x2 +  : : :  xk;1 ) . . (x1  x2  : : :  xk;1 + ) (x1  x2  : : :  xk;1 ) 31 akkor az alabbi k input azonos levelbe vezet: P ;1 x ; ) (x1 +  x2  : : :  xk;1  N ; Pki=1 i ;1 x ; ) (x1  x2 +  : : :  xk;1  N ; ki=1 i . . P ;1 (x1  x2  : : :  xk;1 +  N ; Pki=1 xi ; ) k ; 1 (x1  x2  : : :  xk;1  N ; i=1 xi ) Ez a 3.5 Tetel miatt azt jelenti, hogy ez a k input egyazon 1-monokromatikus cilinder metszetben van Mivel a fenti inputok lathatoan egy csillagot Pk;1 alkotnak,

gy a 3.4 Tetel ertelmeben a csillag kozeppontja, (x1  x2  : : :  xk;1  N ; i=1 xi ; ) is ebben az 1-monokromatikus cilinder-metszetben van. Ami nyilvanvaloan ellentmondas, hiszen ezen inputra a tagok osszege N ; , gy a protokoll 0 eredmenyt kell adjon.  3.30 MEGJEGYZE S: Konnyen belathato, hogy k (N )  k k ( Nk ) , ebb}ol az el}oz}o tetel ugy fogalmazhato, hogy C k(ENk ) = (log k (N )). Azaz utobbi ket tetelunk a EkN fuggveny pontos nagysagrendjet adjak a k (N ) fuggvenyeben, viszont sajnos a k (N ) erteke nem ismert. Egyedul k = 3 mellett ismert egy jo becsles, ui. tudjuk, hogy p ( N )  exp ( log N log log N ). 3 Mas alternatva a protokoll denialasara E fejezet vegen felhvnank a gyelmet arra, hogy a protokoll fogalmanak denialasa sem egyertelm}u a tobbszerepl}os kommunikacio eseten. A protokollt eddig a ketszerepl}os modell mintajara ugy denialtuk a ,,homlokra ragasztott szam" modellben is, hogy olyan

fuggveny, mely kijeloli azt, hogy mikor ki szol, illetve vegeteres eseten a vegeredmenyt az elhangzott bitek fuggvenyeben. Illetve megmondja, hogy a szolasra kovetkez}o jatekos milyen bitet mondjon a jatekos inputja, es az elhangzott bitek fuggvenyeben. Azert denialtukgy a protokoll fogalmat minden esetben, hogy biztostsuk, hogy a jatekosok szamara mindig egyertelm}u legyen, hogy ki kovetkezik szolasra, illetve a protokoll vegen minden jatekos ugyanarra a vegeredmenyre gondoljon. Viszont egyszer}uen ugy is denialhatjuk a protokoll fogalmat, hogy utobbi tulajdonsagait feltetelkent szabjuk meg neki A szakdolgozat szerz}ojenek tudomasa szerint a most kovetkez}o protokoll dencioval meg nem vizsgalta senki a ,,homlokra ragasztott szam" modellt. 3.31 DEFINICIO : Szemelyre szolo protokollnak nevezunk egy tetsz}oleges kommunikacios modellben egy olyan fuggvenycsoportot, melyben minden szerepl}ohoz tartozik egy

fuggveny, ami egy adott pillanathoz megmondja, hogy ez a szerepl}o kovetkezik-e szolasra, es ha igen milyen bitet mondjon, illetve ha veget ert a kommunikacio, akkor mi a vegeredmeny. Mindezt a jatekos inputja, es az elhangzott bitek fuggvenyeben teszi E mellet teljesul, hogy: Minden pillanatban pontosan egy jatekos gondolja, hogy }o kovetkezik szolasra, kiveve, ha veget ert a kommunikacio (ilyenkor persze egy sem), ekkor pedig minden szerepl}o ugyanarra a vegeredmenyre gondol. Lathato, hogy a kulonbseg a szolasra kovetkez}o jatekos kijeloleseben, es a vegeredmeny meghatarozasaban rejlik. Mg a hagyomanyos protokoll minden jatekos szamara elerhet}o 32 adatokbol, es ezert minden jatekos szamara egyertelm}uen kozolte, hogy ki kovetkezik szolasra, addig a szemelyre szolo protokoll eseten a jatekosok nem tudjak, hogy ki a szolasra kovetkez}o, csak annyit tudnak, hogy eppen }ok jonnek, vagy sem. E mellet

feltetelkent szabtuk meg, hogy egyertelm}u legyen, ki kuldjon eppen bitet Ezen tul szemelyre szolo protokollnal azt is megengedjuk, hogy a jatekos altal gondolt vegeredmeny is fuggjon a jatekos inputjatol, szinten feltetelkent megszabva, hogy ez minden jatekosnal ugyanaz legyen. Konnyen latszik, hogy: 3.32 A LLITA S: A Yao-fele ketszerepl}os kommunkacios modellben a hagyomanyos es a szemelyre szolo protokoll fogalma megegyezik. Bizonytas: Egy hagyomanyos protokoll olyan fuggvenyekb}ol all, melyek az A es B jatekosok kozotti kommunikacio fuggvenyeben hatarozzak meg a kovetkez}o jatekost, illetve vegeteres eseten a vegeredmenyt. Az elkuldend}o bit meghatarozasa megegyezik a ket esetben. Igy egy hagyomanyos protokoll megfelel egy szemelyre szolo protokollnak, az ugyanis meg ennel tobb dolog fuggvenyeben hatarozza meg az el}obbieket. Pontosabban a szolasra kovetkez}o jatekost, es vegeredmenyt

kijelol}o fuggvenyb}ol mindket jatekosnak adva egy-egy peldanyt egy szemelyre szolo protokollt kapunk. Azt kell meg megmutatni, hogy a ketszerepl}os modellben a szemelyre szolo protokollnal a jatekos szolasra kovetkezese, es a vegeredmeny tenylegesen nem fugghet a jatekos inputjatol. Ez pedig azert igaz, mert kulonben letezne olyan x x 2 X , y 2 Y , es s bitsorozat, hogy az s elhangzasa utan, ha B-nel y input van, es A-nal x, akkor A azt hiszi, hogy }o jon szolasra, viszont ha A-nal x van, akkor azt hiszi, hogy B kovetkezik. Ez biztosan nem lehet, ugyanis B is gondol valamelyikukre, gy az egyik esetben egyszerre probalnanak beszelni. S}ot a k szerepl}os tablas kommunikacios modellben is egybeesik a ket fogalom, ha az inputok kozott nincs atfedes (mindenki csak egy inputot lat), a fenti bizonytas ekkor is m}ukodik. Viszont a ,,homlokra ragasztott szam" modellben a hagyomanyos, es szemelyre szolo

protokollok elternek. Lathato peldaul, hogy egy szemelyre szolo protokoll megengedi azt, hogy a P2 P3 : : :  Pk jatekosok kozul a mindannyiuk szamara elerhet}o x1 input alapjan d}oljon el, hogy ki kovetkezik szolasra. Ez azt eredmenyezi, hogy a kommunikacios komplexitasa is kulonboz}o lehet egy fuggvenynek a ket protokollfogalom mellett. Nezzunk meg erre egy egyszer}u peldat: Legyen k = 3, es f az a fuggveny, amelyre f (x1  x2  x3 ) ertek az x2 els}o bitjevel egyezik meg ha x1 els}o bitje 0, es x3 els}o bitjevel egyezik meg, ha x1 els}o bitje 1. 3.33 A LLITA S: Erre az f -re CS3 (f ) < C 3(f ), ahol az S az indexben a szemelyre szolo protokollokra utal. Bizonytas: Szemelyre szolo protokollt tudunk adni 1 bit kommunikacioval, hiszen azt mondjuk, hogy x2 kovetkezzek szolasra, ha x1 els}o bitje 1, es x3 kovetkezik szolasra, ha x1 els}o bitje 0. Ekkor a szolasra kovetkez}o jatekos latja a vegeredmenyt, es gy

fel tudja rni a tablara. Viszont hagyomanyos protokoll legalabb 2 bit kommunikaciot igenyel, ugyanis egy 1 bites kommunikacioban a bitet felro jatekost mindent}ol fuggetlenul kell kijelolni, es barkit is jelolunk ki, konnyen adhato olyan input, melyre az a jatekos nem tudja az eredmenyt felrni. 33 Az a kerdes, hogy a ket kommunikacios komplexitas kozott mekkora elteres lehet. Mint lattuk a szemelyre szolo dencio altalanosabb a hagyomanyosnal, gy CSk (f )  C k (f ) mindig teljesul, de mennyivel lehet CSk (f ) kisebb. Erre egy fels}o korlatot tudunk adni 3.34 TE TEL: (k + 1)CSk (f ) + 1  C k(f ) minden f -re Bizonytas: Egy szemelyre szolo protokollbol mindig tudunk keszteni egy hagyomanyosat a kovetkez}okeppen. Amikor a szemelyre szolo protokoll szerint egy jatekos felr egy bitet a tablara, akkor meg ez el}ott minden jatekosrjon fel egy-egy bitet indexuk szerinti sorrendben, meghozza 1-est

pontosan az a jatekos rjon, aki szolasra kovetkezik. Ezzel a modostassal mar egy hagyomanyos protokollhoz jutottunk, hiszen a tablan lev}o bitekb}ol mindig megmondhato, hogy ki kovetkezik szolasra. Esetleg szukseg lehet meg egy bitre, az eredmeny felrasara, hisz elkepzelhet}o, hogy ez nem tortent meg, es a jatekosok meg inputjuktol is fugg}oen gondolnak valamilyen vegeredmenyre. Ebb}ol kovetkezik a tetel Sejthet}o esetleg, hogy ez mar majdnem eles, es adhato olyan f fuggveny, amelyre korulbelul egy (k ; 1) szorzoval nagyobb a hagyomanyos ertelemben vett kommunikacios komplexitas. Ennek bizonytasahoz azonban mindenkeppen valami uj technikara lenne szukseg. Ugyanis konnyen latszik, hogy a protokoll fa adott levelebe erkez}o inputok halmaza az altarnatv protokoll dencio mellett is cilinder metszetet alkot Ezaltal az also becslesi technikak mind m}ukodnek ekkor is, gy ha elterest szeretnenk bizonytani,

ugy a hagyomanyos komplexitasra mas modszerrel kell adnunk egy jobb also becslest. 34 4. A csillag modell A csillag modellben, melyet e szakdolgozatban els}okent vizsgalunk k jatekos, P1 P2  : : :  Pk vesz reszt, egy-egy inputtal a f0 1gn-b}ol. Mindegyikuk kapcsolatban all egy k +1-edik, kozponti P0 jat ekossal, aki azonban nem rendelkezik inputresszel. Igy kell a k szerepl}oknek egy f : (f0 1gn) ;! f0 1g fuggveny erteket kiszamoljak minimalis kommunikacio felhasznalasaval, ahol a kommunikacio a k kapcsolaton elhangzott kommunikaciok osszege. Tehat az 1 fejzetben ismertetett kategorizalassal ez a modell szemelyes kommunikacion alapulo modell, ahol a kommunikacios graf egy k agu csillag, es inputresszel a kozponti jatekoson kvul mindenki rendelkezik. 3.abra Ez a modell a 2. fejezetben targyalt linearis halozatra annyiban hasonlt, hogy az inputtal rendelkez}o jatekosok input nelkuli kozbuls}o szerepl}okon

keresztul kenytelenek kommunikalni A 3 fejezetbeli modellel pedig az a kozos vonas, hogy sok szerepl}o rendelkezik inputtal. Nezzuk meg, hogyan kell e modellben a megengedett protokollt denialni ahhoz, hogy akar a 2. fejezetben egy olyan aszinkron modellt kapjunk, melyben egy protokoll mindig lefuttathato, es minden lefutasa ugyanazon bitsorozatokat eredmenyezi valamennyi kapcsolaton: Minden kapcsolathoz rendeljunk itt is egy protokoll fat, mely azon a kapcsolaton addig elhangzott bitek fuggvenyeben meghatarozza, hogy a ket jatekos kozul melyik kovetkezik szolasra, illetve ha mar egyikuk sem, akkor szamukra mi a vegeredmeny. Ha egy kapcsolaton az inputtal rendelkez}o jatekos kovetkezik szolasra, akkor a protokoll megadja, hogy a jatekos az inputja, es a kapcsolaton addig elhangzott bitek fuggvenyeben milyen bitet kuldjon a kozpontnak. Az aszinkronitas miatt ezt a bitet barmikor elkuldheti, de a szandekos blokkolas kikuszobolese

erdekeben veges id}on belul ezt meg is kell tennie. A protokollhoz tartozik meg k fuggveny, 1 2 : : :  k , ahol i fuggveny azt adja meg, hogy ha az i-edik kapcsolaton a P0 kovetkezik szolasra, akkor az osszes kapcsolaton addig elhangzott bitek fuggvenyeben a kozpont milyen bitet kuldjon a Pi-nek. A i ertekkeszlete f0 1 ?g , es ? az ertek pontosan akkor, ha az i-edik kapcsolaton nem a kozpont kovetkezik szolasra, vagy a kozpont meg biteket var mas jatekosoktol ahhoz, hogy eldontse, milyen bitet kuldjon Pi-nek. A szukseges feltetelek hasonloak a linearis halozatra tettekkel: (1) Konzisztencia a protokoll fakkal: Ha az i-edik kapcsolaton adott pillanatban Pi kovetkezik szolasra, akkor e pillanatban a i erteke ? (azaz a kozpont nem szolhat). (2) Nincs szandekos blokkolas: Ha egyik kapcsolaton sem az inputtal rendelkez}o jatekos kovetkezik szolasra (azaz minden kapcsolaton vagy P0 jon, vagy mar nincs tovabbi

kommunikacio), es a protokoll meg nem fejez}odott be, akkor letezik olyan i, hogy a i erteke nem ?. (3) A kozpont nem gondolhatja meg magat: Ha i erteke nem ?, akkor ez az ertek mar nem valtozhat meg tovabbi kommunikacio hatasara. (4) Egyhangusag: Ha a protokoll befejez}odott, akkor a k kapcsolathoz tartozo protokoll fak azonos eredmenyt jelent}o levelben kotottek ki. Ez a vegeredmeny A linearis halozatnal azt vizsgaltuk meg, hogy az ottani kommunikacios komplexitas hogyan viszonyul a hagyomanyos ketszerepl}os modellbelihez. Itt a csillag modellben viszont a szerepl}ok egy k-valtozos fuggvenyt szamtanak ki, ezert kapcsolatot csak olyan 35 modellbeli kommunikacios komplexitassal kereshetunk, ahol ugyanez all fenn. A modell, amelyhez viszonytunk az a modell lesz, amelyben kk szerepl}o - mindegyike sajat inputtal a f0 1gn -b}ol - szeretne kiszamtani egy f : (f0 1gn ) ;! f0 1g k -valtozos fuggveny erteket

tablas kommunikacikoval (ld. 1 fejezet) Ezt a modellt a tovabbiakban tablas modellnek hvjuk majd. Jelolje a tovabbiakban egy k-valtozos f fuggveny kommunikacios komlexitasat a tablas modellben CkT (f ), a csillag modellben pedig Ck(f ). Mind also, mind fels}o becslest fogunk adni a Ck(f )-re a Ck (f ) fuggvenyeben. 4.1 TE TEL: Ck(f )  k CkT (f ) Bizonytas: Tekintsunk egy optimalis, azaz CkT (f ) bitet hasznalo protokollt az f kiszamtasara a tablas modellben. Amikor az i-edik jatekos e protokoll szerint felr a tablara egy bitet, akkor a csillag modellben a Pi jatekos kuldje el a bitet a kozpontnak, aki pedig tovabbtsa az osszes tobbi k ; 1 jatekosnak. Igy a csillag modellben szimulaljuk a tablas kommunikaciot, hiszen valoban minden bitr}ol minden jatekos tudomast szerez. A tablas modellbeli minden bithez k darab bit elkuldese szukseges e szimulaciohoz, tehat a tetelbeli fels}o becsles valoban fennall.

4.2 TE TEL: Ha f nem konstans, akkor Ck(f )  CkT (f ) + (k ; 1) Bizonytas: Tekintsunk egy optimalis, azaz Ck(f ) bitet hasznalo protokollt az f kiszamtasara a csillag modellben. Adunk egy protokollt a tablas modellre, mely legfeljebb Ck(f ) kommunikaciot hasznal Amikor az i-edik jatekos (i 6= 0) egy bitet kuld a kozpontnak a csillag modellben, akkor a tablas modellben az i-edik jatekos rja fel ezt a bitet a tablara. Amennyiben egyszerre tobb inputtal rendelkez}o jatekos is szolasra kovetkezik, akkor koztuk valamilyen el}ore meghatarozott sorrend (peldaul indexuk) dontse el, hogy kit szimulalunk el}oszor. Ezek utan amikor a kozpont kuld egy bitet peldaul a j edik jatekosnak a csillag modellben, akkor a tablas modellben ne tortenjek semmi Nem is kell, hiszen a kozpont az elkuldott bitet a hozza addig beerkezett bitekb}ol szamolta ki, ezek viszont mind a tablan vannak, gy a j -edik jatekos ezt maga is kiszamolhatja.

Igy a tablas modellre adott protokoll annyival kevesebb bitet hasznal a csillag modellbelinel, ahany bit a kozpontbol tovabbtodott valamely inputtal rendelkez}o jatekos fele. Ebb}ol persze Ck (f )  CkT (f ) azonnal kovetkezik, meghozza az f -re tett feltetel nelkul is. Azt hogy a tetel is igaz azt a kovetkez}okben igazoljuk. Ha f nem konstans, akkor a csillag modellben minden kapcsolaton el kell legalabb egy bitnek hangzania valamilyen iranyban, hiszen ha mondjuk az i-edik kapcsolaton nincs kommunikacio, ez azt jelentene, hogy Pi szamara a vegeredmeny semmit}ol sem fugg, tehat f konstans. Ha a csillag modellbeli kommunikacio soran minden inputtal rendelkez}o jatekoshoz erkezik bit a kozpontbol, akkor legalabb k bitet megsporolunk a tablas modellben a fenti szimulacioval. Akkor van csak gond, ha valamely inputtal rendelkez}o jatekos, mondjuk Pi nem kap bitet a kozpontbol. Ez azt jelenti, hogy }o az inputjabol mar biztosan tudja a

vegeredmenyt, azaz nala egy a fuggveny erteket rogzt}o input van. Ha egyetlen jatekosnal van csak rogzt}o input, akkor (k ;1) bitet meg mindig megsporolunk. Tegyuk fel, hogy tobb jatekosnal is lehet rogzt}o input. Vegyuk eszre, hogy ekkor ezek csak ugyanazt a fuggvenyerteket rogzthetik, kulnben ellentmondas lenne, ha az egyik jatekos egy nullat, masik pedig egy 1-et rogzt}o inputot kapna. Legyen Pi a legkisebb index}u jatekos, aki 36 rogzt}o inputot kapott. Az i-edik kapcsolaton ez esetben is kell kommunikacionak tortennie, amely tehat kizarolag Pi -t}ol a kozpont fele iranyul. Tehat valamilyen bitsorozattal Pi tajekoztatja a kozpontot, hogy }o mar tudja a vegeredmenyt. Modostsuk ekkor a fenti tablas szimulacionkat ugy, hogy amennyiben Pi ezt a jelsorozatot rja fel a tablara, akkor a jatekosok azonnal tudjak a vegeredmenyt, ezaltal nincs is szukseg tovabbi kommunikaciora. Igazabol a

jatekosok csak azt tudjak meg, hogy Pi -nel rogzt}o input van, de mint lattuk ez csak egyfele fuggvenyerteket rogzthet, gy a vegeredmenyt is tudjak. Ekkor az i-nel nagyobb sorszamu kapcsolatokon meg nem hangzott el bit, es mivel lattuk, hogy legalabb egy bit el fog hangzani, gy ezeket mind megsporoltuk. Az i-nel kisebb sorszamu kapcsolatokon pedig szinten megsporoltunk legalabb egy-egy bitet, hisz azokon kuldott, vagy kuldeni fog a kozpont kifele bitet. O sszefoglalva tehat barhogy is zajlik a csillag modellben a kommunikacio, a tablas modelllben (k ; 1) bitet megsporolva szimulalhatjuk azt, ebb}ol pedig adodik a tetel. A tovabbiakban azt vizsgaljuk, hogy a 4.1 es 42 Tetelek altal adott becslesek mennyire elesek. A most kovetkez}o tetel azt mondja, hogy a 41 Tetel becslese eles 4.3 TE TEL: Letezik olyan f fuggveny, melyre Ck(f )  k CkT (f ) ; k2 Bizonyt as: Legyen az f a k-valtozos egyenl}oseg fuggveny,

vagyis az az k f : (f0 1gn) ;! f0 1g fuggveny, melyre f (x1  x2  : : :  xk ) = 1 pontosan akkor, ha x1 = x2 = = xk all fenn. Akkor CkT (f )  n + (k ; 1), hiszen eleg ha P1 felrja a tablara a teljes inputjat, majd ezek utan a tobbi (k ; 1) jatekos egy-egy bitet kuld, amely 1-es ha az }o inputja megegyezik a felrttal, es 0, ha nem. Ekkor az f erteke pontosan akkor 1, ha a (k ; 1) utoljara felrt bit mind 1-es. Megmutatjuk, hogy az egyenl}oseg fuggvenyre a csillag modellben Ck(f )  kn. Ebb}ol Ck(f )  kn  k(CkT (f );(k;1)) = k CkT (f );k(k;1), ami igazolja a tetelt. Vegyunk ennek erdekeben egy jo protokollt a csillag modellben az egyenl}oseg fuggveny kiszamtasara. Legyen x y 2 f0 1gn, ekkor azt alltjuk, hogy az (x x : : :  x) es az (y y : : :  y) input kas mellett egy adott (tetsz}oleges) kapcsolaton mas bitsorozatok hangzanak el. Ugyanis ha peldaul az i-edik kapcsolaton ugyanaz a kommunikacio hangzana el az (x x : : : 

x) es az (y y : : :  y) input k-asok mellett, akkor ugyanez a bitsorozat hangzana el az i-edik kapcsolaton akkor is ha Pi jatekos y-t, az osszes tobbi pedig x-et kapna inputjaul. Hiszen a fPj : j 6= ig jatekoscsoport nem tudja, hogy Pi -nel milyen input van, gy koztuk ugyanaz tortenik ha Pi -nel az x illetve az y van, amennyiben persze }o is ugyanazokat a biteket kuldi. Ugyangy Pi sem tudja, hogy a tobbi inputtal rendelkez}o jatekosnal csupa x, vagy csupa y input van. Viszont ez ellentmondas, hiszen ha az i-edik kapcsolaton a kommunikacio ugyanaz ha Pi-nel y van, a tobbieknel pedig x, illetve ha mindenkinel x van, akkor Pi a kommunikacio vegen ugyanarra a vegeredmenyre is gondol, viszont az eredmeny az els}o esetben 0, az utobbiban pedig 1. Ebb}ol persze az is kovetkezik, hogy minden kapcsolat eseten a rajta elhangzo bitsorozatok halmaza prex-mentes halmazt alkot, mid}on az input vegigfut az f(x x : : :  x) : x 2 f0 1gng halmazon.

Jelolje sl (x) az l-edik kapcsolaton elhangzott bitsorozatot az (x x : : :  x) input mellett. Akkor alkalmazva a prex-mentes 37 halmazokra vonatkozo 2.4 Lemmat azt kapjuk, hogy k X X x2f01gn l=1 jsl (x)j = k X X l=1 x2f01gn jsl (x)j  k 2n log 2n = 2n kn Ebb}ol viszont kovetkezik, hogy letezik olyan x 2 f0 1gn, hogy az (x x : : :  x) input mellet az osszes kommunikacio legalabb kn. A 4.2 Tetelben szerepl}o (k ; 1)-es kulonbseg a ket kommunikacios komplexitas kozott biztosan nem javthato k-nal nagyobbra, ugyanis ha az egyenl}osegtesztet nezzuk az inputok els}o bitjeire, akkor ennek a fuggvenynek a kommunikacios komplexitasa konnyen igazolhato, hogy a tablas modellben k (mindenki felrja az els}o bitet a tablara), a csillag modellben pedig 2k (mindenki bekuldi az els}o bitjet a kozpontba, az pedig mindenkit ertest az eredmenyr}ol). Ilyen ertelemben tehat eles a 42 Tetel becslese Igazabol viszont az az erdekes

kerdes, hogy teljesul-e valamilyen k-tol fugg}o c  1-re, hogy Ck(f )  c CkT (f ) + F (k) , ahol F (k) valamilyen k-tol fugg}o hibatag. Ezt nem tudjuk, gy a 4.2 Tetel nem tekinthet}o elesnek, viszont tudjuk, hogy a c-t az (1 + k;1 1 ) ertek alatt erdemes csak keresni, hiszen: 4.4 TE TEL: Majdnem minden f : (f0 1gn)k ;! f0 1g fuggvenyre (n ! 1 eseten) Ck(f )  (1 + k;1 1 ) CkT (f ) + k. Bizonytas: Azt tudjuk, hogy Ck(f )  kn + k , hiszen a csillag modellben minden fuggvenyre alkalmazhato a trivialis protokoll, mely soran valamennyi szerepl}o bekuldi az inputjat a kozpontba (kn bit), majd a kozpont az f ertekenek kiszamtasa utan az eredmenyr}ol minden jatekost tajekoztat (tovabbi k bit). Eleg ha megmutatjuk, hogy CkT (f )  (k ; 1)n teljesul majdnem minden f fuggvenyre, ugyanis ebb}ol Ck(f )  kn + k = k ;k 1 (k ; 1)n + k  k ;k 1 CkT (f ) + k ami a bizonytando alltas. A bizonytas leszamlalassal tortenik. Az f : (f0

1gn)k ;! f0 1g fuggvenyek szama fnk = 22nk , hiszen (f0 1gn)k -nak 2nk eleme van, es egy fuggveny e halmaz minden elemehez ketfele erteket rendelhet. A tablas modellben at legfeljebb t bitet hasznalo protokollok szama (amit pt jelol) becsulhet}o felulr}ol a (2k)2 22n 2t ertekkel, hiszen egy protokoll a tablas modellben ket fuggvenyb}ol all. Az egyik az addig tablara kerult bitek fuggvenyeben megadja, hogy ki kovetkezik szolasra, amennyiben persze meg nem ert veget a protokoll. Pt;1 2i Mivel ekkor a tablan lev}o bitek szama legfeljebb (t ; 1), gy ezt legfeljebb k i=0 -felekeppen teheti meg. Ha pedig mar veget ert (ekkor legfeljebb t bit van a tablan), akkor at protokoll meghatarozza a tabla fuggv enyeben a vegeredmenyt, erre tehat legfeljebb 22 lehet}oseg P ;1 2i  2t azt kapjuk, hogy az eddigiek meghatarozasara van. Kihaszntalva, hogy ti=0 legfeljeb (2k)2 lehet}oseg van. A protokoll masik fuggvenye az ily modon

kijelolt jatekos inputjanak, es a tabla addigi tartalmanak fuggvenyeben adja meg, hogy a kijelolt jatekos 38 2n 2t modja lehet. Vagyis azt kaptuk, milyen bitetrjont a tanbltara. Ennek viszont legfeljebb 2 hogy pt  (2k)2 22 2 = 22t(2n+log k+1). Amennyiben t = (k ; 1)n ; 1, es log k + 1  2n;1 (ez utobbi feltehet}o, hisz n ! 1 esetet nezzuk), akkor 2t (2n + log k + 1)  43 2nk : Ebb}ol pt  22t(2n+log k+1)  2; 14 2nk fnk 22nk ami nullahoz tart n ! 1 eseten. Viszont pt a legfeljebb t bitet hasznalo protokollok szama, tehat felulr}ol becsli a legfeljebb t kommunikacios komplexitasu fuggvenyek szamat, gy ezen fuggvenyek aranya az osszes fuggvenyek kozott 0-hoz tart. Ez pedig azt jelenti, hogy majdnem minden fuggveny kommunikacios komplexitasa a tablas modellben legalabb (k ; 1)n. Mivel ez a legjobb also hatar, amit Ck(f )-fel el tudtunk erni, gy sejthetnenk azt is, hogy minden f -re Ck(f )  (1 + k;1 1 )CkT (f )

teljesul. Azonban ez biztosan nem igaz Erre eppen a 2. fejezetben lathattunk egy ellenpeldat Vegyuk ugyanis eszre, hogy k = 2 mellett a Tiwari fele linearis halozat modell megegyezik a csillag modellel.A sejtes k = 2 mellett, azt alltana, hogy C2 (f )  2 C2T (f ) , ami eppen Tiawri sejtese a 2 hosszu linearis halozatra, amir}ol megmutattuk, hogy nem igaz. Tiwari sejtesere az ellenpelda egy olyan f fuggveny volt, melyre ottani jelolessel elve Ck (f )  ( 43 + o(1)) k C (f ) teljesult. Viszont k = 2 mellett az ottani C2(f ), mint emltettuk azonos az e fejezetben denialt C2(f )-fel, es az ottani C (f ), azaz a hagyomanyos ketszerepl}os kommunikacios komplexitas pedig termeszetesen megegyezik a ketszerepl}os tablas modellbeli komplexitassal, amit pedig e fejezetben C2T (f )-fel jelolunk. A tterve tehat az e fejezetben hasznalt jelolesekre olyan f -et ismerunk a 2. fejezetb}ol, amelyre C2 (f )  ( 34 + o(1)) 2 C2T (f ) = ( 23 +

o(1)) C2T (f ) Ha azonban a protokolokra mind a tablas, mind a csillag modellben egy igen er}os megkotest teszunk, akkor ez az eddig rossz sejtes igazza, es ezaltal a 4.4 Tetel elesse valik Ez az er}os megkotes pedig a ,,nemtor}odom" tulajdonsag. Azt mondjuk egy protokollra, hogy nemtor}odom protokoll, ha az, hogy mikor ki szoljon a jatekosok kozul az nem fugg az addig elhangzott bitekt}ol, es ezaltal az inputoktol sem. A protokoll tehat el}ore megmondja, hogy mikor, ki, kinek kuld egy bitet. 4.5 TE TEL: Ha a tablas modellben, es a csillag modellben egyarant csak nemtor}odom protokollokat engedunk meg, es az uj komplexitasokat kalappal kulonboztetjuk meg az eddigiekt}ol, akkor minden f fuggvenyre teljesul, hogy C^k(f )  (1 + k;1 1 ) C^kT (f ) Bizonytas: Tekintsunk egy optimalis, azaz C^k(f ) bitet hasznalo nemtor}odom protokollt az f kiszamtasara a csillag modellben. Konstrualunk egy nemtor}odom protokollt a

tablas modellre, amely legfeljebb (1; k1 ) C^k(f ) bitet hasznal, ebb}ol C^kT (f )  (1; k1 ) C^k(f ), amib}ol a tetel atrendezessel kovetkezik. Legyen Pl az a jatekos, aki az adott nemtor}odom protokoll eseten a legkevesebb bitet kommunikalja a kozponttal. Ez tehat ebben az esetben nem fugg az inputoktol Tekintsuk a tablas modellben a kovetkez}o protokollt: 39 Amikor a csillag modellben Pi jatekos bekuld egy bitet a kozpontba (i 6= l), akkor a tablas modellben a Pi jatekos felrja ezt a bitet a tablara, ha viszont a csillag modellben Pl kuld bitet a kozpontnak, akkor a tablas modellben nem tortenik semmi. Szinten nem tortenik semmi, ha a kozpont kuld bitet Pl-nek. Vegezetul ha a kozpont kuld a csillag modellben egy bitet a Pi (i 6= l) jatekosnak, akkor ezt a bitet a tablas modellben a Pl jatekos fogja felrni a tablara. Ezt azert tudja megtenni, mert a kozpont az alapjan donti el, hogy milyen bitet kuld a Pi-nek, hogy

milyen biteket kapott eddig a jatekosoktol. Amiket a Pj (j 6= l) jatekosoktol kapott, azok fenn vannak a tablan, gy Pl birtokaban van az osszes kommunikacionak, hogy szimulalja a kozpont tevekenyseget. A tablas modellregy egy olyan protokollt adtunk, amelyben a csillag modellhez kepest megsporoltuk azt a kommunikaciot, amely a kozpont es Pl kozott zajlott. Ez legalabb 1 ^ k Ck (f ) bit megtakartast jelent, hiszen a Pl a legtobbet, es gy legalabb a kommunikacio k-ad reszet kommunikalta a kozponttal. 4.6 MEGJEGYZE S: Ha nem tesszuk fel a nemtor}odom tulajdonsagot a megengedett protokollokrol, hanem a szokvanyos modon ertelmezzuk azokat (tehat az, hogy mikor ki kovetkezik, az az addig elhangzott bitektol is fugg), akkor ezzel a modszerrel is csak annyit tudunk bizonytani, hogy Ck(f )  CkT (f ). Hiszen azt, hogy melyik kapcsolaton fogjuk megsporolni a kommunikaciot az inputoktol fuggetlenul kellett megadnunk, es

el}ofordulhat olyan input, melyre ezen a kapcsolaton csak minimalis az elhangzo kommunikacio. 4.7 MEGJEGYZE S: Ha csak a nemtor}odom protokollokkal foglalkozunk, attol meg a 4.4 Tetel igaz marad, ugyanis a csillag modellben a trivialis protokoll is egy nemtor}odom protokoll, es a leszamlalas is ugyanugy m}ukodik, mint a hagyomanyos protokoll ertelmezessel. Azzal a kut lonbseggel, hogy annak kijelolesere, hogy mikor ki beszel nemt csak hogy legfeljebb k2 lehet}oseg van, hanem ennel kevesebb: kt, de ett}ol meg a k2 fels}o becsles csak meg inkabb igaz. Ebb}ol az latszik, hogy a nemtor}odom protokollokra a C^k(f )  (1 + k;1 1 ) C^kT (f ) egy eles also becsles. Azonban a nemtor}odom tulajdonsag egy igen er}os megkotes a protokollokra, amit peldaul az is mutat, hogy Tiwari sejtese nemtor}odom protokollokra szortkozva azonnal igazza valna. Radasul rendkvul egyszer}uen igazolhato is: Tekintsuk a linearis halozat ketszerepl}os

szimulaciojat barmely kapcsolat menten. Akkor leteznek olyan x y inputok, melyek mellett ezen a kapcsolaton C^ (f ) bit hangzik el. Mivel egy nemtor}odom protokoll az inputoktol fuggetlenul adja meg, hogy mikor ki beszel, gy minden kapcsolatra kenytelen C^ (f ) bit kommunikaciot kijelolni. Ebb}ol azonnal kovetkezik a C^k (f )  k C^ (f ) alltas O sszefoglalva tehat eddigi eredmenyeinket arra jutottunk, hogy nemtor}odom protokollok eseten (1 + k;1 1 ) C^kT (f )  C^k(f )  k C^kT (f ) , ahol raadasul a becsles mindket oldalrol eles. A hagyomanyos modon ertelmezett protokollok eseten viszont azt tudjuk, hogy CkT (f ) + (k ; 1)  Ck(f )  k CkT (f ) , es az also iranybol nem tudjuk, hogy eles-e a becsles. 40 Felhasznalt irodalom: 1] E. KUSHILEVITZ, N NISAN, Communication Complexity, Cambridge University Press, Cambridge, 1997 2] P. TIWARI, Lower Bounds on Communication Complexity in Distributed Computer Networks, J Assoc Comput Mach

34, 921-938, 1987 3] E. KUSHILEVITZ, N LINIAL, R OSTROVSKY, The Linear-Array Conjecturec in Communication Complexity is False, In Proc. of the 28th Annual ACM Symposium on Theory of Computing, 1-10, 1996 4] M. DIETZFELBINGER, The Linear-Array Problem in Communication Complexity Resolved, In Proc of the 29th Annual ACM Symposium on Theory of Computing, 373-382, 1997 5] L. BABAI, N NISAN, M SZEGEDY, Multiparty Protocols and Logspace-hard Pseudorandom Sequences, In Proc. of the 21st Annual ACM Symposium on Theory of Computing, 1-11, 1989 6] A. K CHANDRA, M L FURST, R J LIPTON, Multi-party Protocols, In Proc of the 15th Annual ACM Symposium on Theory of Computing, 94-99, 1983 7] F. R K CHUNG, Quasi-random Classes of Hypergraphs, Random Structures and Algorithms, Vol 1, No 4, 363-382, 1990 8] F. R K CHUNG, P TETALI, Communication Complexity and Quasi Randomness, SIAM J Discrete Math , Vol 6, No 1, 110-123, 1993 9] R. RAZ, The BNS-Chung Criterion for Multi-party Communication

Complexity, manuscript 10] V. GROLMUSZ, The BNS Lower Bound for Multi-party Protocols is Nearly Optimal, Information and Computation, 112(1), 51-54, 1994 11] M. MARCUS, H MINC, A survey of Matrix Theory and Matrix Inequalities Allyn and Bacon, Boston, Mass. , 1964 12] A. AHO, J ULLMAN, M YANNAKAKIS, On Notions of Information Transfer in VLSI Circuits, In Proc. of the 15th Annual ACM Symposium on Theory of Computing, 133-139, 1983 41