Többszereplős kommunikációs komplexitás

SZAKDOLGOZAT Készítette: Róka Dániel Témavezetők: Tardos Gábor

Katona Gyula Absztrakt:

A Yao által definiált két szereplős kommunikációs modell lehetőséget kínál a szereplők száma szerinti általánosításra. Ennek rengeteg különböző módja lehet, melyek közül többet is megpróbálunk áttekinteni. Egy ilyen lehetőség a lineáris hálózat, melyet P. Tiwari vetett fel egy 1987-es cikkében, majd erdeményei 1996-97-ben lettek pontosítva. A ,,homlokra ragasztott szám” modell az előbbitől igen eltér. Ebben is ismert több eredmény. Mind alsó, mind felső becslések akadnak szép számmal bizonyos függvények kommunikációs komplexitására, melyek azonban nem teljesen kielégítőek, hiszen minden eddig ismert alsó becslés a szereplők számának növekedésével exponenciálisan csökken. E két modell részletes vizsgálatán kívül felvetünk egy új kommunikációs modellt: a csillag modellt, melyet a jelen szakdolgozat vizsgál először.

Tartalom:

1. Többszereplős kommunikációs komplexitás

2. A lineáris hálózat

3. A ,,homlokra ragasztott szám” modell

4. A csillag modell 1. Többszereplős kommunikációs komplexitás

A Yao féle kétszereplős kommunikáció

A Yao féle kommunikációs modellben két játékos, A és B mindegyike rendelkezik egyegy saját inputtal. A számára x ∈ X, B számára pedig y ∈ Y ismert, ahol X, illetve Y a játékosok számára lehetséges inputok halmazai. Egy f : X × Y ⟶ {0, 1} függvény mellett szeretnék f(x, y)-t kiszámítani, mégpedig úgy, hogy a lehető legkevesebb bitet kelljen egymásnak elküldeni. A játékosok tetszőleges mennyiségű számítást végezhetnek, csak az egymásnak elküldött információért kell ,,fizetni”. Egy ún. kommunikációs protokoll meghatározza, hogy egy adott pillanatban véget ért-e már a kommunikációs folyamat, ha igen, akkor mi a keresett függvényérték, ha nem, akkor pedig melyik játékos mondjon egy bitet, és az milyen bit legyen. Hogy mikor ki beszéljen az csak az addig elhangzott bitektől függhet azért, hogy ne legyen egyszerre beszélésre lehetőség. Végetérés esetén a végeredményt szintén csak az elhangzott bitektől tehetjük függővé, hiszen ez mindkét játékos számára ugyanaz kell legyen. Végül az, hogy ki mit mond az elhangzott bitek, és a szólásra következő játékos inputjának függvénye. Egy P protokoll hossza a leghosszabb bitsorozat hossza, amely az adott protokoll mellet elhangozhat a két játékos között, azaz ha P(x, y) jelöli a két játékos között elhangzott bitsorozatot a P protokoll és x, y inputok mellett, akkor |P| = max_{x∈X,y∈Y} |P(x, y)|. Az f függvény kommunikációs komlexitása pedig a legrövidebb f-et számoló protokoll hossza, tehát C(f) = min |P| , ahol a minimalizálás az f-et helyesen kiszámoló protokollokra történik.

C(f) lehetséges kiszámításával, illetve becslésével részletesen most nem foglalkozunk, csak néhány alapvető tényt jegyezzünk meg:

1.1 TÉTEL: Amennyiben az inputok n bitesek, akkor C(f) ≤ n + 1

Bizonyítás: A triviális protokollal pl. A egyszerűen elküldheti az egész x-et B-nek, aki így kiszámíthatja f(x, y)-t és egyetlen bittel A-t is tájékoztathatja az eredményről. ⋄

1.2 DEFINÍCIÓ: Az f : X × Y ⟶ {0, 1} függvény kommunikációs mátrixa az az M_{f} mátrix, melynek sorait X, oszlopait Y elemeivel azonosítjuk, és x ∈ X, y ∈ Y esetén (M_{f})_{xy} = f(x, y)

1.3 DEFINÍCIÓ: Az M_{f} mátrix egy részmátrixa monokromatikus, ha a részmátrix minden eleme azonos. Ekkor a részmátrixnak megfelelő X^{∗} × Y^{∗} ⊆ X × Y halmazt is (az f-re nézve) monokromatikusnak mondjuk.

1.4 TÉTEL: Ha az f függvény M_{f} mátrixának monokromatikus részmátrixokkal való lefedéséhez szükség van legalább t monokromatikus részmátrixra, akkor C(f) ≥ ⌈log t⌉.

(Itt is, és továbbiakban is mindenhol a logaritmus kettes alapú.)

Bizonyítás: Minden kommunikációs protokollhoz rendelhetünk egy bináris fát, az ún. protokoll fát, melynek csúcsait megjelöljük az A és B betűk valamelyikével aszerint, hogy az adott pillanatban az A vagy a B játékos következik szólásra. A csúcsból kiinduló két élre nullát illetve egyet írunk, és attól függően, hogy a szólásra következő játékos milyen bitet mond, a megfelelő irányba megyünk tovább. A protokoll fa leveleiben a protokoll véget ér, tehát a játékosok tudják a végeredményt. Azon (x, y) inputpárokra, melyekre egy rögzített ℓ levélben kötünk ki, az f(x, y) ezért ugyananazt az értéket adja, jelöljük ezen inputpárok halmazát a továbbiakban R_{ℓ}-lel. Az R_{ℓ} egy részmátrixa M_{f}-nek ugyanis amikor az A (illetve B) játékos elküld egy bitet, ezzel az M_{f}-ből bizonyos sorokat (illetve oszlopokat) kizár, a számára lehetséges inputpok halmaza pedig a maradékra korlátozódik. Az M_{f} ilyen függőleges és vizszintes szabdalásával valóban egy részmátrix keletkezik. Vagyis R_{ℓ} az M_{f} mátrixban egy monokromatikus részmátrixot ad, így a protokoll fa levelei az M_{f}- et monokromatikus részmátrixokra partícionálják. Ha a tétel feltétele teljesül, akkor a protokoll fának legalább t levele kell legyen, ami egy bináris fa esetén csak úgy lehetséges, ha a mélysége legalább ⌈log t⌉. ⋄

1.5 DEFINÍCIÓ: Az f : X × Y ⟶ {0, 1} függvényre egy

T = {(x_{i}, y_{i}) : i ∈ {1, … t}} ⊆ X × Y ún. t méretű becsapós halmaz, amennyiben (1) f(x_{i}, y_{i}) = z ∀i ∈ {1, …, t} , ahol z ∈ {0, 1} rögzített, továbbá

(2) ha (x_{i}, y_{i}), (x_{j}, y_{j}) ∈ T, és i ≠ j,akkor f(x_{i}, y_{j}) = z̄ és f(x_{j}, y_{i}) = z̄ közül legalább az egyik igaz, ahol z̄ = 1 − z a z negáltja.

1.6 TÉTEL: Ha az f függvény M_{f} mátrixa tartalmaz t méretű becsapós halmazt, akkor C(f) ≥ ⌈log t⌉.

Bizonyítás: Vegyük észre, hogy egy becsapós halmaz semely két eleme nem lehet az f függvény M_{f} mátrixának ugyanabban a monokromatikus részmátrixában. Ebből az 1.4 Tétel felhasználásával könnyen adódik a tétel. ⋄

1.7 TÉTEL: Ha az f függvény mátrixa M_{f}, akkor C(f) ≥ log rangM_{f}.

Bizonyítás: Ha az M_{f} mátrixot t darab monokromatikus részmátrixra partícionáljuk, akkor az M_{f} előáll M_{f} = ∑_{i=1}^{t} M_{i} alakban, ahol M_{i} az i-edik monokromatikus részmátrixa M_{f}-nek, kibővítve nullákkal a részmátrixon kívül. Azaz

(M_{i})_{xy} = \{ \begin{matrix}(M_{f})_{xy} & ha (x, y) az i-edik monokromatikus részmátrixban van \\ 0 & egyébként. \end{matrix}

Kihasználva, hogy rang(M_{i}) ≤ 1 és rang(A + B) ≤ rang(A) + rang(B) , azt kapjuk, hogy rang(M_{f}) = rang(∑_{i=1}^{t}(M_{i})) ≤ ∑_{i=1}^{t} rang(M_{i}) ≤ t. Amiből az 1.4 Tétellel következik a kívánt eredmény. ⋄

Az általánosítás lehetőségei

Amennyiben a Yao féle kommunikációt szeretnénk több szereplőre kiterjeszteni, több lehetőség is kínálkozik az általánosításra. Nézzünk most végig egy párat ezen alternatívák közül.

Amikor a kommunikációban több játékossal dolgozunk, a legfontosabb, amit el kell döntenünk, hogy a szereplők között miként zajlik a kommunikáció. Beszélhetünk személyes kommunikációról, amikor mindig csak két szereplő beszélhet egymással. Ekkor arról is kell nyilatkoznunk, hogy mely játékos-párok között engedünk meg információáramlást. Ez azt jelenti, hogy mondjuk k darab játékos esetén a \binom{k}{2} játékos-pár mindegyikéről el kell dönteni, hogy létesítünk-e közöttük kapcsolatot. Ezekkel a döntésekkel tulajdonképpen egy gráfot definiálunk a k szereplőn, mint csúcsokon úgy, hogy a gráf élein engedjük meg a kommunikációt. Ekkor megőrizzük a Yao féle kétszereplős modellnek azt a tulajdonságát, hogy a kommunikáció két játékos között zajlik. Ha viszont a kétszereplős modellből inkább azt szeretnénk átvinni a többszereplős modellbe, hogy egy elküldött bitről minden játékosnak tudomása van (ami nyilván teljesül a kétszereplős modellben) , akkor egy ún. táblás kommunikációt kapunk, amelyben a szólásra következő játékos mindig egy bitet ír fel egy olyan képzeletbeli táblára, melynek tartalmát az összes játékos láthatja. Az előbbi modellben egy bit elküldésének árán csak egy, míg utóbbiban az összes játékos hozzájut a bitben megtestesülő információhoz, így nyilvánvaló, hogy ugyanazon függvény kiszámítása az utóbbi modellben jóval könnyebb, azaz kevesebb (vagy legalábbis nem több) bit elküldését teszi szükségessé. A két lehetőség akár keverhető is egymással, így lehetnek egyszerre két szereplő közötti kapcsolatok és a játékosok bizonyos részhalmazaihoz rendelt táblák is a modellben, ami tulajdonképpen azt jelenti, hogy a gráf, amellyel meghatározzuk a szereplők közötti kapcsolatokat egy hipergráf, ahol a 2-nél több csúcsot tartalmazó élek a megfelelő táblák. Ez utóbbi eset viszont annyira bonyolult, hogy nem fogunk vele részletesebben foglalkozni.

Hasonlóan az előbbihez arról is döntenünk kell, hogy a kétszereplős modellből azt a tényt vigyük át, hogy az összes szereplő rendelkezik saját inputtal, vagy azt, hogy pontosan két szereplő rendelkezik inputtal. Utóbbi esetben az új játékosoknak nem adunk inputot, ők egy kezdeti, üres állapotból indulnak. Szintén többféle lehetőség kínálkozik az általánosításra aszerint, hogy egy-egy inputrészt hány játékos számára teszünk hozzáférhetővé. Ez a kérdés természetesen a kétszereplős modellben fel sem vetődött, azonban ha 2-nél több szereplő rendelkezik inputtal, akkor egy inputot nem feltétlenül csak egy játékosnak adhatunk ki. Meghatározhatjuk minden egyes inputrészhez, hogy a játékosok mely csoportjának adunk ehhez hozzáférési jogot. Ennek egy igen szélsőséges esetével fogunk találkozni a 3. fejezetben, ahol egy-egy játékosnak majdnem az összes inputrészhez lesz hozzáférési lehetősége.

Vegyük észre, hogy nem sok értelme lenne a táblás kommunikációt azzal az esettel kombinálni, amikor csak két szereplő rendelkezik inputtal, hiszen ez a jól ismert kétszereplős kommunikációs modellt adná vissza, néhány új játékossal kiegészítve, akiknek viszont semmi beleszólása nem lenne az eseményekbe.

A Yao féle kommunikáció lényeges tulajdonsága, hogy nem az időt tekinti lényegesnek, hanem csak az elküldött bitek számát, ugyanis korlátlan számítási lehetőséget biztosít a két játékosnak. Ezt szeretnénk átvinni mindenképpen a többszereplős modellekre is. Éppen ezért a személyes kommunikáción belül csak az úgynevezett aszinkron modellekkel fogunk foglalkozni, melyekben az idő semmilyen szerephez nem jut. Lehetőség lenne ugyanis szinkron modelleket is vizsgálni, ahol ugyan a korlátlan számítási lehetőséget meghagynánk, de a sok kapcsolaton elhangzó bitek között valamilyen egyidejűséget, és egymásutániságot néznénk. A célunk tehát az időfogalom teljes kiküszöbölése, mint azt a lineáris hálózat modelljének pontos definícióján keresztül jól fogjuk majd látni.

Az aszinkronitás biztosítása azonban még nem teszi egyértelművé, hogy milyen feltételeket szabjunk a megengedett protokolloknak. Az egyszerre beszélést, és egyéb zavarokat a legegyszerűbben úgy küszöbölhetjük ki, ha az, hogy mikor ki következik szólásra csak a kapcsolatokon addig elhangzott bitek függvénye. Ez meg is felelne a kétszereplős modellben használt protokollfogalomnak. Viszont ha egy többszereplős modellben egy x inputhoz több játékosnak is van hozzáférése, akkor az, hogy közülük ki lesz a következő bitküldő függhet akár az x inputtól is anélkül, hogy ez zavarokat okozna.

Látható tehát, hogy számtalan fajta többszereplős modellt lehet definiálni. A következőkben két igen eltérő modellt fogunk részletesen megvizsgálni. A 2. fejezetbeli lineáris hálózat személyes kommunikáción alapul, és csak két szereplő rendelkezik saját inputtal, míg a 3. fejezetbeli ,,homlokra ragasztott szám” modellben a kommunikáció táblás, és inputja minden játékosnak van méghozzá úgy, hogy a hozzáférés is elég különös, ugyanis egy játékos majdnem minden inputot lát. Ezek után pedig megnézünk egy új lehetőséget, a csillag modellt, ami mindkét előbb említett modellel tartalmaz néhány közös vonást, és jelen szakdolgozat új kutatási témáját képezi.

2. A lineáris hálózat

A modell

Egyik lehetséges módja a többszereplős kommunikációs modell definiálásának, ha a Yao féle kétszereplős modellt bővítjük ki további szereplőkkel, akiknek azonban nem adunk inputrészt. Tehát továbbra is csak két kitűntetett játékos rendelkezik az x ∈ X, illetve y ∈ Y inputtal, és egy kétváltozós f : X×Y ⟶ {0, 1} függvényt szándékoznak kiszámítani. Viszont több új szereplő is bekapcsolódik a játékba úgy, hogy a szereplőkre, mint pontokra illesztett G gráffal meghatározzuk, hogy ki kivel beszélgethet. Egy kommonikációs folyamat hosszát az egyes kapcsolatokon (gráféleken) elhangzott bitek számainak összegével definiálhatjuk. Egy f-re adott protokoll hossza természetesen a leghosszabb előforduló kommunikáció hossz a lehetséges (x, y) inputok mellett, és az f kommunikációs kompexitása a G gráf által meghatározott kommunikációs modellben így C_{G}(f) = min_{P} |P| , ahol P megengedett protokoll f számolására a G gráffal adott többszerelős modellben.

Amennyiben a G gráfot egy k hosszú útnak választjuk a két kitűntetett játékos között, akkor a P. Tiwari által felvetett lineáris hálózathoz jutunk. E modellben tehát k+1 játékos (P_{0}, P_{1}, …, P_{k}) vesz részt. P_{0} x-et, P_{k} y-t ismeri, a többi játékosnak nincsen semmilyen információja. A játékosok egy utat alkotnak, tehát kapcsolata P_{i}-nek csak P_{i−1}-gyel és P_{i+1}-gyel van. (A kitüntetett P_{0}-nak és P_{k}-nak persze csak egy beszélgetőpartnere van.) Az f(x, y)-t kommunikációs komplexitását e modellben jelölje C_{k}(f).

1.abra

Vegyük észre, hogy akármilyennek is választanánk a G gráfot ekvivalens problémát kapnánk a lineáris hálózat modellel, hiszen a két inputtal rendelkező játékosnak az aszinkron modellünkben kizárólag a köztük lévő legrövidebb út mentén lesz célszerű kommunikálni.

Yao már korábban felvetette e modell valamivel egyszerűbb változatát, amelyben a kommunikáció csak az egyik irányban zajlik, tehát a kisebb indexű játékostól a nagyobb indexű felé. E modellben az idő kizárása egyáltalán nem jelent gondot, nem úgy, mint a Tiwari féle kétirányú modellben. Nagyon fontos ezért, hogy utóbbit pontosan definiáljuk. A Yao féle egyirányú hálózatot is meg fogjuk vizsgálni, de most nézzük meg hogyan kell a kétirányú modellt jól, tehát aszinkron módon definiálni:

Tekintsük úgy az x, y inputokat, mintha azok a virtuális nulladik illetve (k + 1)-edik kapcsolaton hangzanának el rögtön a kommunikáció kezdetekor. Egy adott pillanatban s_{i}- vel jelöljük az i-edik kapcsolaton addig elhangzott bitek sorozatát. Egy a lineáris hálózatra adott protokoll több részből áll. Tartalmaz minden kapcsolathoz egy-egy protokoll fát, mely, akár a kétszereplős modellben meghatározza a két szereplő közötti kommunikáció lefolyását. Azaz megadja, hogy mikor melyik játékos következik szólásra az adott kapcsolaton, illetve ha a kommunikáció már véget ért az adott kapcsolaton, akkor mi az eredmény. Mindezeket persze az adott kapcsolaton addig elhangzott bitek függvényében mondja meg. Tartalmaz továbba minden 1 ≤ i ≤ k -hoz (azaz minden kapcsolathoz) két függvényt, ezek

Φ_{i}^{+}, Φ_{i}^{−} : {0, 1}^{∗} × {0, 1}^{∗} ⟶ {0, 1, ⊥}

\begin{matrix}Φ_{i}^{+} : (s_{i−1}, s_{i}) ⟼ Φ_{i}^{+}(s_{i−1}, s_{i}) , \\ Φ_{i}^{−} : (s_{i}, s_{i+1}) ⟼ Φ_{i}^{−}(s_{i}, s_{i+1}) . \end{matrix}

Ezek a függvények megmondják, hogy az i-edik kapcsolaton balról, illetve jobbról milyen bitet küldjön P_{i−1} illetve P_{i} játékos. A ⊥ azt jelenti, hogy most nem küldhet bitet. Ez lehet azért, mert ezen a kapcsolaton nem ő következik szólásra, vagy akár azért, mert még további biteket vár a másik oldalról, mielőtt eldönti, hogy milyen bitet küldjön erre az oldalra. Amennyiben például Φ_{i}^{+}(s_{i−1}, s_{i}) = 1, akkor a P_{i−1} ezt az egyes bitet elküldheti P_{i}-nek most, vagy akármikor a későbbiekben. Ha megfelelő feltételeket szabunk egy protokollnak, akkor ezek biztosítani fogják, hogy ez értelmes legyen, ne tudjon megállni, és valóban aszinkron legyen. Ezek a feltételek a következők:

(1) Konzisztencia a protokoll fákkal: Ha az i-edik kapcsolathoz rendelt protokoll fa adott pillanatban egy P_{i}-vel megjelölt csúcsban, vagy egy levélben van, akkor e pillanatban a Φ_{i}^{+}(s_{i−1}, s_{i}) = ⊥ (azaz P_{i−1} nem szólhat), hasonlóan fordítva.

(2) Nincs szándékos blokkolás: (a) Ha az i-edik, és (i + 1)-edik kapcsolaton (1 ≤ i < k) egyaránt P_{i} következik szólasra, akkor Φ_{i}^{−}(s_{i}, s_{i+1}), és Φ_{i+1}^{+}(s_{i}, s_{i+1}) közül legalább az egyik nem ⊥.

(b) Ha az i-edik (0 ≤ i < k)kapcsolaton a kommunikáció befejeződött, és az i+1-edik kapcsolaton P_{i} következik szólásra, akkor Φ_{i+1}^{+}(s_{i}, s_{i+1}) ≠ ⊥. Hasonlóan a másik oldalra.

(3) Senki sem gondolhatja meg magát: Ha Φ_{i}^{+}(s_{i−1}, s_{i}) ≠ ⊥ (1 ≤ i ≤ k), továbbá az s_{i−1}^{∗} = s_{i−1}t_{i−1} az s_{i−1} meghosszabítása, akkor Φ_{i}^{+}(s_{i−1}^{∗}, s_{i}) = Φ_{i}^{+}(s_{i−1}, s_{i}).

(4) Egyhangúság: Ha a protokoll befejeződött, akkor a k kapcsolathoz tartozó protokoll fák azonos eredményt jelentő levélben kötöttek ki. Ez a protokoll által kiszámolt eredmény.

Ha a modellt a fenti feltételekkel definiáljuk, akkor egyszerűen igazolható a most következő lemma, ami minden további eredményhez nélkülözhetetlen.

2.1 LEMMA: Adott protokoll egy adott (x, y) input mellet midig lefuttatható, és minden lefuttatása esetén ugyanazokat a kommunikációkat eredményezi minden egyes kapcsolaton.

A későbbiekben gyakran szükségünk lesz a következő lemmára, ami a 2.1 Lemma teljesülése miatt nem kíván bizonyítást.

2.2 LEMMA: Amennyiben rögzítünk egy kapcsolatot, pl. az l-ediket (1 ≤ l ≤ k), úgy a hálózatnak megfeleltethetünk egy kétszereplős kommunikációs modellt, melyben az A játékos szimulálja a {P_{0}, P_{1}, …, P_{l−1}}, a B pedig a {P_{l}, P_{l+1}, …, P_{k}} játékosok tevékenységét. Ekkor az l-edik kapcsolaton elhangzott bitsorozat a hálózatban, és a kétszereplős modell kommunikációs bitsorozata megegyezik.

Az 1. fejezetben a kétszereplős kommunikációs modell definiálásakor már tisztáztuk, hogy az, hogy mikor ki beszél az csak az addig elhangzott bitektől függ. Ennek következménye, hogy azon bitsorozatok, melyek elhangozhatnak a két szereplő közötti kommunikáció során egy ún. prefix-mentes halmazt alkotnak, azaz a halmaznak nem lehet két olyan eleme, hogy az egyik a másik prefixe (kezdőszelete). Ugyanis ha lenne két ilyen bitsorozat, akkor a rövidebbik elhangzása után nem lenne egyértelmű mindkét játékos számára, hogy véget ért a kommunikáció, vagy esetleg egyikük még szólásra következik.

Ha ezt a gondolatmenetet a lineáris hálózat kétszereplős szimulációjával együtt használjuk, az alábbi fontos lemmát kapjuk:

2.3 LEMMA: A lineáris hálózat tetszőleges kapcsolatát rögzítve, a különböző inputok mellett az ezen kapcsolaton elhangzó bitsorozatok egy prefix-mentes halmazt alkotnak.

Egy ilyen halmazról a következőt tudjuk:

2.4 LEMMA: Ha S = {s_{1}, s_{2}, …, s_{t}} egy prefix-mentes részhalmaza {0, 1}^{∗}-nak, akkor ∑_{j=1}^{t} |s_{j}| ≥ t · log t.

Bizonyítás: Minimalizáljuk adott t mellett a ∑_{j=1}^{t} |s_{j}| (összhossz) értéket, amikor S = {s_{1}, s_{2}, …, s_{t}} prefix-mentes halmaz. Amennyiben léteznek i, j ∈ {1, 2, …, t} indexek, hogy s_{j} legalább 2 bittel hosszabb s_{i}-nél, akkor s_{i}, s_{j} elhagyásával, és helyettük s_{i}0 valamint s_{i}1 bitsorozatok S-be bevételével az összhossz nem nő, viszont a hosszak négyzetösszege csökken. Ezért az összhossz a minimumát biztosan felveszi olyan S halmaz mellett, amelyre az s_{i}-k hosszai közötti eltérések maximuma 1. Legyen tehát most S ilyen.

Ebben az esetben a legrövidebb bitsorozathosszúságok, amik előlfordulhatnak azok ⌊log t⌋ és ⌊log t⌋ + 1, ennél rővidebb elemekből ugyanis biztosan nem lehet egy t elemű prefix-menets halmazt összeállítani. Jelölje c, hogy hány ⌊log t⌋ hosszú szó van, ekkor persze a ⌊log t⌋ + 1 hosszú szavak száma t − c. Az összhossz minimalizálása most már csak a c maximalizálását jelenti.

Egyrészt nyilván c ≤ 2^{⌊log t⌋}, másrészt viszont egy ⌊log t⌋ hosszú szó kizárja két ⌊log t⌋+1 hosszú szó S-be kerülésének lehetőségét (azt a kettőt, amelyeknek ő prefixe), így kapunk egy másik feltételt is c-re, méghozzá azt, hogy legalább annyi szóbajöhető ⌊log t⌋+1 hosszú szó marad, amennyi kell, azaz t−c ≤ 2^{⌊log t⌋+1} −2c. Ez átalakítva c ≤ 2^{⌊log t⌋+1} −t. Viszont könnyen látszik, hogy a második feltétel mindig erősebb (2^{⌊log t⌋} ≥ 2^{⌊log t⌋+1} − t). Az optimum tehát c = 2^{⌊log t⌋+1} − t. Ebből az optimális összhossz

c⌊log t⌋ + (t − c)(⌊log t⌋ + 1) = (2^{⌊log t⌋+1} − t)⌊log t⌋ − 2^{⌊log t⌋+1}(⌊log t⌋ + 1) =
= t⌊log t⌋ + 2(t − 2^{⌊log t⌋})

Ez tehát a ∑_{j=1}^{t} |s_{j}| minimális értéke. Hogy ez nagyobb t · log t -nél az pedig abból látszik, hogy amennyiben t egy 2-hatvány, akkor láthatóan egyenlőség áll fenn. Két szomszédos 2-hatvány között viszont ⌊log t⌋ állandó, így a minimális érték e darabon lineáris függvény, mely mivel a t · log t függvény konvex (második deriváltja pozitív), ezért a t · log t függvénygörbéje felett halad.⋄

Yao egyirányú hálózata

Az egyszerűség kedvéért nézzük először a Yao által vizsgált speciális esetét a lineáris hálózatnak, amikor a játékosok közötti kapcsolatok csak egyirányúak, tehát amikor P_{i} a P_{i+1}-nek tud küldeni információt, de fordítva nem. Ekkor természetesen csak azt kívánjuk meg egy protokollról, hogy a végére P_{k} tisztában legyen az f(x, y) értékkel. Ebben az esteben a következő pontos eredményt tudjuk, ha C\overrightarrow{k}(f)-val jelöljük e modellben a kommunikációs komplexitást:

2.5 TÉTEL: Ha M_{f}-nek pontosan t különböző sora van, akkor

⌈k log t⌉ ≤ C\overrightarrow{k}(f) ≤ k⌈log t⌉.

Bizonyítás: A felső becslés triviális, hisz P_{0}-nak csak az inputnak megfelelő sor számát kell végigküldenie a hálózaton. Nézzük tehát az alsó becslést: Legyen x_{1}, x_{2}, …, x_{t} olyan t input, melyekhez tartozó M_{f}-beli sorok páronként különbözőek. Jelölje s_{l}(i) azt a bitsorozatot, amely az l-edik kapcsolaton (P_{l−1} és P_{l} között) hangzik el, ha P_{0} inputja x_{i}. Az egyirányú adagyovábbítás következtében ez tényleg csak a P_{0}-nál lévő inputtól függ. Az, hogy x_{i} és x_{j} sora különbözik M_{f}-ben azt jelenti, hogy létezik olyan y ∈ Y, melyre f(x_{i}, y) ≠ f(x_{j}, y). Ha s_{l}(i) = s_{l}(j) lenne valamely l, i, j értékekre, akkor f(x_{i}, y) = f(x_{j}, y) állna ∀y ∈ Y mellett, ami viszont ellentmondás. Ezért s_{l}(i) ≠ s_{l}(j) kell legyen minden l, i, j esetén, azaz egy rögzített kapcsolaton áthaladó bitsorozat minden különböző x_{i} inputra más és más. Az {s_{l}(i) : 1 ≤ i ≤ t} halmaz így t különböző bitsorozatból áll, és azt is tudjuk (2.3 Lemma), hogy prefix-mentes halmaz, ebből a 2.4 Lemma alkalmazásával adódik, hogy

∑_{j=1}^{t} ∑_{l=1}^{k} |s_{l}(j)| = ∑_{l=1}^{k} ∑_{j=1}^{t} |s_{l}(j)| ≥ ∑_{l=1}^{k} t log t = k · t · log t.

Ahol ∑_{l=1}^{k} |s_{l}(j)| éppen a teljes kommunikáció hossza az x_{j} input mellett, így a bal oldalon álló kifejezés nem más, mint a kommunikációk hosszainak összege a különböző x_{j} inputok mellett. Ezért az erre kapott alsó becslésünkből skatulya-elvvel következik, hogy létezik olyan j, melyre a kommunikáció hossza ≥ ⌈k log t⌉. ⋄

Tiwari sejtése

Térjünk most vissza a Tiwari féle hálózati modellhez, ahol mindkét irányban zajlik a kommunikáció.

Amennyiben a lineáris hálózatban a közbülső, tehát inputtal nem rendelkező játékosoknak csak azt a feladatot adjuk, hogy továbbítsák az információt a két kitüntetett játékos között, akkor az így kapott protokoll tulajdonképpen egy kétszereplős kommunikáció azzal a különbséggel, hogy egy bit elküldése helyett ugyanezt k-szor kell megtenni. Ebből az adódik, hogy C_{k}(f) ≤ k · C(f) , ahol C(f) az f hagyományos (kétszereplős) kommunikációs komplexitása. Segíthetnek-e a közbülső játékosok ennél hatékonyabban egy függvény kiszámításában, azaz szigorú-e az egyenlőtlenség, amit az előbb felírtunk? Vagy talán egyenlőség áll, és semmilyen más protokoll nem jobb az egyszerű adattovábbításnál?

E fejezetben be fogjuk bizonyítani a következő, Tiwaritól származó (ld. [2]) tételt:

2.6 TÉTEL: Majdnem minden f függvényre teljesül, hogy C_{k}(f) ≥ k(C(f) − 1).

A majdnem minden szót úgy kell érteni, hogy egy véletlenszerűen választott f : {0, 1}^{n} ×{0, 1}^{n} ⟶ {0, 1} függvényre 1-hez tartó valószínűséggel igaz a tétel (n → ∞).

Ebből Tiwari azt sejtette, hogy a 2.6 Tétel minden f függvényre fennáll. Hogy a sejtés nem igaz, azt később látni fogjuk, most azonban igazoljuk a 2.6 Tételt. A továbbiakban az egyszerűség kedvéért az X, Y inputalaphalmazok a {0, 1}^{n} legyenek.

Mint azt az 1.6 Tételben láttuk, az f függvény kommunikációs mátrixában egy becsapós halmaz jelenléte lehetőséget adott C(f) alsó becslésére. Hasonlót állíthatunk a lineáris hálózaton:

2.7 TÉTEL: Ha az f függvény M_{f} mátrixa tartalmaz t méretű becsapós halmazt, akkor C(f) ≥ ⌈k · log t⌉.

Bizonyítás: Legyen T = {(x_{i}, y_{i}) : 1 ≤ i ≤ t} egy t méretű becsapós halmaz M_{f}- ben, és jelölje s_{l}(i) az l-edik kapcsolaton elhangzott bitsorozatot az (x_{i}, y_{i}) input mellett. Az l-edik kapcsolat mentén vehetjük a kétszereplős szimulációját a hálózatnak (2.2 Lemma). Ebből ha s_{l}(i) = s_{l}(j) állna fenn valamilyen i, j ∈ {1, …, t} mellett, akkor f(x_{i}, y_{i}) = f(x_{i}, y_{j}) = f(x_{j}, y_{i}) = f(x_{j}, y_{j}) lenne, ami ellentmond annak, hogy T egy becsapós halmaz. Itt tulajdonképpen egy a későbbiekben kimondandó lemma (2.10 Kicserélési lemma) speciális esetét alkalmaztuk. Ebből rögzített l-re az s_{l}(i) bitsorozatok minden ire különbözőek, innen pedig a bizonyítás vége egy az egyben a 2.5 Tétel bizonyításának végével egyezik meg. ⋄

Ez azt jelenti, hogy egy kellően nagy becsapós halmaz jelenléte M_{f}-ben azt eredményezi, hogy C(f) n-hez, C_{k}(f) pedig kn-hez lesz közeli, ebből következően Tiwari sejtése igaz, ha megfelelően nagy (2^{n}-hez közeli) méretű becsapós halmaz létezik M_{f}-ben. Mivel azonban egy általános f-re leggtöbbször nem mutatható ki egy ilyen nagy becsapós halmaz jelenléte, így a log-rang módszer irányába fogunk továbbmenni, előbb azonban egy kis előkészítésre lesz szükség.

2.8 DEFINÍCIÓ: Legyen P egy protokoll az f(x, y) függvény kiszámítására a lineáris hálózaton. A P kommunikációs gráfja az a G_{P} gráf, melyet a következőképpen kapunk:

Jelölje S_{l} bitsorozatok azon halmazát, melyek valamilyen (x, y) input mellett elhangozhatnak az l-edik kapcsolaton. Tekintsük úgy, hogy az x illetve y inputok a P_{0} illetve P_{k} játékosok számára a képzeletbeli nulladik illetve (k + 1)-edik kapcsolaton hangzanak el. Ekkor G_{P} pontjai k + 2 halmaz elemei. E halmazok: X = S_{0}, S_{1}, S_{2}, …, S_{k}, S_{k+1} = Y. G_{P} egy szintezett gráf az S_{l} halmazokkal (0 ≤ l ≤ k + 1), mint szintekkel, élek csak a szomszédos szintek, tehát S_{l} és S_{l+1} között vezetnek. Az S_{l} és S_{l+1} közötti élek halmaza, E_{l} a következőképpen van definiálva (l ∈ {0, 1, …, k}) :

E_{l} = {(s_{l}, s_{l+1}) : Létezik (x, y) ∈ X × Y , hogy f(x, y) = 1 és s_{l}, s_{l+1} megjelennek, mint kommunikáció az l-edik illetve (l+1)-edik kapcsolatokon az f(x, y) számítása közben}

2.abra

2.9 DEFINÍCIÓ: A G_{P} gráfban ,,hosszú út”-nak nevezünk egy k + 1 élű utat, mely az X = S_{0} halmaz egy x elemét köti össze az Y = S_{k+1} halmaz egy y elemével, és minden S_{l} halmazból pontosan egy elemet érint.

Világos, hogy amennyiben f(x, y) = 1, úgy (x, y) input mellett a protokoll futtatása után a kapcsolatokon megjelenő bitsorokkal mint köztes pontokkal egy ,,hosszú út” van G_{P}-ben x és y között. Ennek viszont a megfordítása is igaz, mint azt a 2.11 Tételben látni fogjuk. Előbb azonban következzék egy nagyon fontos lemma:

2.10 LEMMA (KICSERÉLÉSI LEMMA): Ha az (x, y) és (x^{∗}, y^{∗}) inputpárok esetén a P protokoll mellett a kapcsolatokon rendre az (s_{1}, s_{2}, …, s_{k}) illetve a (s_{1}^{∗}, s_{2}^{∗}, …, s_{k}^{∗}) bitsorozatok jelennek meg a kommunikáció során, és az l-edik kapcsolaton ugyanaz az s_{l} = s_{l}^{∗} jön létre, akkor az (x, y^{∗}) inputpár mellett az (s_{1}, s_{2}, …, s_{l−1}, s_{l}, s_{l+1}^{∗}, …, s_{k}^{∗}) fog a kapcsolatokon létrejönni.

Bizonyítás: A lemma állítása egyszerűen következik abból, hogy az l-edik kapcsolattól balra lezajló kommunikációk csak az l-edik kapcsolaton elhangzó bitektől, és a P_{0} játékosnál lévő inputtól függenek. Mivel a lemma feltételei mellett mindkettő azonos az (x, y) és (x, y^{∗}) inputpárok esetén, így az első l − 1 kapcsolaton ugyanaz a bitsorozat kell elhangozzon a két inputpár mellett. Ugyanígy az l-edik kapcsolattól jobbra lévő kapcsolatokon az (x, y^{∗}) és az (x^{∗}, y^{∗}) inputpárok eredményezik ugyanazt a kommunikációt.

Hasonló gondolatmenettel igazolható, hogy az (x^{∗}, y) inputpár pedig az (s_{1}^{∗}, s_{2}^{∗}, …, s_{l−1}^{∗}, s_{l}, s_{l+1}, …, s_{k}) bitsorozatokat eredményezi a kapcsolatokon. ⋄

2.11 TÉTEL: G_{P}-ben létezik egy ,,hosszú út” x ∈ X és y ∈ Y között {s_{l} : l = 1, …, k} köztes pontokkal ⟺ f(x, y) = 1 és f(x, y) kiszámítása során az ledik kapcsolaton s_{l} a kommunikációs bitsorozat.

Bizonyítás: A ⟸ irányt már láttuk, így már csak a ⟹ irányt kell megmutatnunk. Az, hogy létezik egy ,,hosszú út” x és y között {s_{l} : l = 1, …, k} köztes pontokkal definíció szerint azt jelenti, hogy léteznek (x_{i}, y_{i}) párok (i = 0, 1, 2, …, k), hogy f(x_{i}, y_{i}) = 1 , x_{0} = x , y_{k} = y és f(x_{i}, y_{i}) számítása mellett s_{i} és s_{i+1} lesz a kommunikáció az iedik illetve (i + 1)-edik kapcsolaton. Teljes indukcióval megmutatjuk, hogy minden j-re (j=0, 1, 2, …, k) igaz, hogy f(x, y_{j}) számolásánál az l-edik kapcsolaton s_{l} a kommunikáció minden 1 ≤ l ≤ (j + 1) esetén. Az indukciós állítás y_{0} választása miatt igaz j = 0-ra. Ha igaz (j − 1)-re, akkor f(x, y_{j−1}) számításánál az első j kapcsolaton a kívánt kommunikáció hangzik el, míg f(x_{j}, y_{j}) számításánál azt tudjuk, hogy a j-edik és (j +1)-edik kapcsolaton s_{j} illetve s_{j+1} a bitsorozat. Ebből a kicserélési (2.10) Lemmával következik, hogy f(x, y_{j})- re már az első (j + 1) kapcsolaton az s_{l}-ek hangzanak el. A j = k esteben (amely éppen igazolja a tételt) a bizonyitás csak annyiban különbözik , hogy nincs (k +1)-edik kapcsolat. ⋄

2.12 KÖVETKEZMÉNY: Legfeljebb egy ,,hosszú út” vezethet G_{P} bármely két pontja között.

Bizonyítás: A 2.11 Tétel és a 2.1 Lemma közös következménye. ⋄

Jelölje A^{i} a G_{P} gráf S_{i} ∪ S_{i+1}-re való megszorításával létrejövő páros gráf adjacencia mátrixát. Akkor:

2.13 LEMMA: M_{f} = A^{0}A^{1} … A^{k} .
Bizonyítás: Jelölje B := A^{0}A^{1} … A^{k}, akkor

B_{xy} = ∑_{s_{1},s_{2},...,s_{k}} A_{xs_{1}}^{0}A_{s_{1}s_{2}}^{1} … A_{s_{k}y}^{k}.

Az összegben egy nem-nulla elem egy ,,hosszú út”-nak felel meg x és y között, így a 2.11 Tétellel és 2.12 Következménnyel B_{xy} = (M_{f})_{xy}. ⋄

2.14 LEMMA: Legyen A_{m×m} a G páros gráf adjacencia mátrixa . Ha A nem szinguláris a valós test felett, akkor G-ben van teljes párosítás.

Bizonyítás: Az A valós test feletti permanense, per(A) megadja a G-ben lévő teljes párosítások számát. Az A nem szinguláris , azaz det(A) ≠ 0 , így az A 0/1 mátrix volta miatt ez azt jelenti, hogy per(A) > 0, ebből pedig G-ben létezik legalább egy teljes párosítás. ⋄

2.15 TÉTEL (BINET-CAUCHY): Legyen A_{m×m} = B_{m×k} · C_{k×m} és legyen k ≥ m. Akkor

det(A) = ∑_{S⊆{1,2,...,k},|S|=m} det(B(S))det(C(S))

ahol B(S) (ill. C(S)) a B (ill. C) azon részmátrixa, melyet az S által megjelölt oszlopok (ill. sorok) kiválasztásával nyerünk.

Bizonyítás: Megtalálható pl. [11]-ben. ⋄

2.16 KÖVETKEZMÉNY: Ha A = BC nem szinguláris, akkor van egy S ⊆ {1, 2, …, k} és |S| = m, hogy B(S) és C(S) is nem szinguláris.

Jelölje G_{i} (i = 0, 1, 2, …, k) azt a páros gráfot, melyet a G_{P} gráf S_{i} ∪ S_{i+1} halmazra való megszorításával nyerünk. Ennek adjacencia mátrixa A^{i}, mint már említettük. Jelölje B^{j} := A^{0}A^{1} … A^{j}. Mint láttuk a 2.13 Lemmában : B^{k} = M_{f}. Most X = Y = {0, 1}^{n} legyen, ekkor |X| = |Y | = 2^{n}.

2.17 TÉTEL: Amennyiben M_{f} nem szinguláris, akkor G_{P}-ben létezik 2^{n} darab pontdiszjunkt ,,hosszú út”, melyek mindegyike különböző X-beli pontból indul, és különböző Y -beli pontba érkezik.

Bizonyítás: Az állítást k-ra (a hálózat hosszára) vonatkozó indukcióval bizonyítjuk. A k = 0 eset ugyan valójában nem létezik, mégis ez lesz az indukció kiindulópontja. Ekkor a képzeletbeli G_{P}-nek két szintje lenne X és Y, azaz páros gráf lenne. Ekkor ha B^{0} = A^{0} nem szinguláris, akkor a 2.14 Lemma szerint a páros gráfban létezik teljes (2^{n} méretű) párosítás. Tegyük fel, hogy k-ra igaz, hogy a k + 2 szinttel rendelkező szintezett G_{P} gráfra ha a B^{k} nem szinguláris, akkor létezik 2^{n} darab pontdiszjunk ,,hosszú út” a két szélső szint között. Ekkor (k+1)-re B^{k+1} = B^{k} ·A^{k+1}, ahol B^{k} egy 2^{n}×|S_{k+1}| méretű, A^{k+1} pedig egy |S_{k+1}|×2^{n} méretű mátrix. Ha B^{k+1} nem szinguláris, akkor a 2.15 Tétel értelmében létezik S ⊆ S_{k+1} , ahol |S| = 2^{n} és B^{k}(S) valamint A^{k+1}(S) nem szinguláris 2^{n} × 2^{n}-es mátrixok. Az indukciós feltevés szerint létezik 2^{n} darab pontdiszjunkt út S_{0} = X és S ⊆ S_{k+1} között. A 2.16 Következmény értelmében pedig az S és S_{k+2} = Y halmazok között létezik teljes párosítás. Az előbbi utakat a párosításbali élekkel meghosszabbítva megkapjuk a kívánt 2^{n} darab pontdiszjunkt utat X és Y között. ⋄

2.18 TÉTEL: Ha M_{f} nem szinguláris, akkor C_{k}(f) ≥ kn.

Bizonyítás: Mivel M_{f} nem szinguláris, így a 2.17 Tétel biztosítja, hogy létezik 2^{n} pontdiszjunk ,,hosszú út” G_{P}-ben. Ha az i-edik út végpontjai x_{i}, y_{i} , akkor a T = {(x_{1}, y_{1}), …, (x_{2^{n}}, y_{2^{n}})} halmaz 2^{n} olyan inputpárból áll, hogy semely kettőnek nem egyezik meg a kommunikációs bitsorozata egyik kapcsolaton sem. A 2.5 Tételbeli skatulya-elvvel azonos módon mutatható meg, hogy ekkor létezik egy j, hogy (x_{j}, y_{j}) mellett az öszes kommunikáció legalább kn bit. ⋄

2.19 KÖVETKEZMÉNY: Ha M_{f} az f függvény mátrixa, akkor

C_{k}(f) ≥ k · log(rang(M_{f})).

Bizonyítás: Ha M_{f} nem nem szinguláris, akkor a 2.18 Tételt alkalmazhatjuk a legnagyobb nem szinguláris részmátrixára, amelynek mérete rang(M_{f}). ⋄

Már csak annyit kell megmutatnunk, hogy egy általános f függvény mátrixának nagy a rangja:

2.20 TÉTEL: Majdnem minden n × n-es 0/1 mátrix rangja ≥ n − f(n) GF (2) felett tetszőleges olyan f függvényre, mely ∞-hez tart n → ∞ esetén.

Bizonyítás: Becsüljük alulról a legalább r rangú 0/1 mátrixok számát, m_{r}-et, méghozzá azon mátrixok számával, melyek első r sora független GF (2) felett: Az első r sor megválasztására ∏_{i=0}^{r−1}(2^{n}−2^{i}) lehetőség van, míg ezek után a mátrixot 2^{n(n−r)} -féleképpen lehet befejezni. Ezért

m_{r} ≥ 2^{n(n−r)} · ∏_{i=0}^{r−1}(2^{n} − 2^{i}).

Az n × n-es 0/1 mátrixokból összesen 2^{n^{2}} =: m van. Így a legalább r rangú mátrixok aránya az összes mátrixok között:

\frac{m_{r}}{m} ≥ \frac{∏_{i=0}^{r−1}(2^{n} − 2^{i})}{2^{nr}} = ∏_{i=0}^{r−1}(1 − \frac{1}{2^{n−i}}) ≥ 1 − ∑_{i=0}^{r−1} \frac{1}{2^{n−i}} ≥ 1 − \frac{1}{2^{n−r}}

Ez pedig r = n − f(n) esetén 1-hez tart. ⋄

A valós test feletti rang ennél már csak nagyobb lehet. Arra jutottunk tehát, hogy a függvények túlnyomó részére a log-rang becslés nagyon jól becsli C(f)-et és C_{k}(f)-et egyaránt, ezekre a függvényekre ezáltal igaz Tiwari sejtése.

A sejtés cáfolata

Mivel Tiwarinak sikerült bizonyítania, hogy majdnem minden f függvényre teljesül, hogy C_{k}(f) ≥ k(C(f) − 1), így azt sejtette, hogy ez tetszőleges f függvényre fennáll. A sejtés cáfolatához olyan függvényt kell konstruálni, melynek kiszámításához a közbülső játékosok intelligensebb módon is hozzájárulhatnak, mint ha csak biteket továbbítanak a két kitűntetett játékos között. Egy ilyen f függvényre C_{k}(f)-et felülről, C(f)-et pedig alulról kell becsülni ahhoz, hogy a sejtést megcáfoljuk. E. Kushilevitz, N. Nisan és R. Ostrovsky [3]-ban olyan végtelen sok függvényből álló osztályt mutattak, melyre

C_{k}(f) ≤ (\frac{3}{4} + o(1)) · k · C(f). (∗)

ahol k tetszőleges páros szám, az o(1) hibatag pedig n → ∞ mellett értendő.

Legyen g : {0, 1}^{n} × {0, 1}^{n} ⟶ {0, 1} egyelőre tetszőleges függvény. Hogy milyen feltételeknek kell eleget tegyen az később fog majd kiderülni. E g segítségével konstruáljunk egy f_{g}-vel vagy egyszerűen csak f-fel jelölt függvényt a következőképpen:

2.21 DEFINÍCIÓ: Legyen f : {0, 1}^{2n} × {0, 1}^{2n} ⟶ {0, 1} az a függvény, amelyre x_{1}, x_{2}, y_{1}, y_{2} ∈ {0, 1}^{n} esetén

f([x_{1}, x_{2}], [y_{1}, y_{2}]) := \{ \begin{matrix}g(x_{1}, y_{2}) & ha g(x_{1}, y_{1}) = 1 \\ g(x_{2}, y_{1}) & ha g(x_{1}, y_{1}) = 0 \end{matrix}

Azt állítjuk, hogy a lehetséges g függvények túlnyomó részére az így definiált f-re fennáll (*), ezt a 2.25 Tétel fogja kimondani. Ehhez C_{k}(f)-et felülről, C(f)-et pedig alulról kell megbecsülni.

2.22 TÉTEL: A fenti f-re C_{k}(f) ≤ \frac{3}{2}k · n + 2k , ha k páros.

Bizonyítás: Adunk egy megfelelő protokollt a k hosszú lineáris hálózaton, amennyiben k páros. Kezdetben P_{0} számára [x_{1}, x_{2}], P_{k} számára [y_{1}, y_{2}] ismert. Küldje el P_{0} az x_{1}-et, P_{k} pedig az y_{1}-et a P_{k/2} ,,középső” játékosnak a \{P_{i} : i = 1, 2, ⋯, \frac{k}{2} −1\} illetve a \{P_{i} : i = \frac{k}{2} + 1, \frac{k}{2} + 2, ⋯, k − 1\} játékosok továbbításával. Ehhez eddig 2 · \frac{k}{2} · n bit kommunikációra van szükség. Ezután P_{k/2} számítsa ki x_{1} és y_{1} ismeretében g(x_{1}, y_{1}) értékét. Amennyiben g(x_{1}, y_{1}) = 1, akkor P_{k/2} küldje el x_{1}-et P_{k}-nak, így ő tudja számolni g(x_{1}, y_{2}) (tehát az f) értékét. Ehhez újabb \frac{k}{2} · n bit szükséges majd a végeredményről P_{k} minden további játékost tájékoztathat k bit kommunikációval. Hasonlóan ha g(x_{1}, y_{1}) = 0, akkor P_{k/2} küldje el P_{0}-nak az y_{1}-et, aki így számolhatja g(x_{2}, y_{1})-et (tehát f-et), stb. Azonban még mielőtt P_{k/2} elküldi például x_{1}-et a P_{k}-nak küldenie kell egy-egy bitet P_{0} és P_{k} játékosok felé, ezzel tájékoztatva őket, hogy inputrészt várjanak, vagy csak a végeredményt. Mondjuk az 1-es azt jelenti, hogy az inputrész következik, a 0 pedig, hogy neki már nincs más dolga, mint megvárni az eredménybitet. Ez még további 2 · \frac{k}{2} , azaz k bit kommunikációt jelent. Az összes kommunikáció \frac{3}{2}kn + 2k , ami igazolja a tételt.⋄

Páratlan k esetén a \frac{3k}{2} helyett mindenhol \frac{3k+1}{2} lenne irandó a bizonyításban, ami egy újab k-tól függő hibatagot eredményezne.

Míg a 2.22 Tétel a g választásától függetlenül igaz, addig C(f) alulról történő becslése nem lehetséges akármilyen g mellett, azonban mint nemsokára kiderül a függvények legtöbbje megfelelő lesz. Válasszuk egyelőre véletszerűen a g függvényt.

Jelölje N := 2^{n}. Legyenek 0 ≤ α ≤ 1 és β ≥ 1 később meghatározandó konstansok. Jelölje továbbá L := βn. Álljon R_{1} az M_{g} (a g N × N-es mátrixának) sorainak L darab diszjunkt párjából, és ugyanígy R_{2} az M_{g} oszlopainak L diszjunkt párjából. Ekkor az R_{1} × R_{2} tartalmaz L^{2} darab 2 × 2-es részmátrixot M_{g}-ből. Az R_{1} × R_{2}-t nevezzük α-kiegyensúlyozottnak, ha a lehetséges 2^{4} = 16 lehetséges 2 × 2-es részmátrix mindegyike legalább αL^{2}-szer előfordul R_{1} × R_{2}-ben.

Definiáljuk a következő feltételt:

(F1) Az α = 1/32 érték mellett az M_{g} mátrix minden 2L × 2L részmátrixa α-kiegyensúlyozott.

2.23 TÉTEL: Majdnem minden g függvényre teljesül az (F1) feltétel.

Bizonyítás: Itt most elhagyjuk az egyébként egyszerű számolást igénylő bizonyítást.⋄

Az alsó becslés folyamatosan használja, hogy g kielégíti az (F1) feltételt, és annak az alábbi közvetlen következményeit.

(F2) Az M_{g} nem tartalmaz L × L méretű monokromatikus részmátrixot.

(F3) Az M_{g} minden 2L × L méretű részmt́rixában a lehetséges 4 darab 2 × 1-es részmátrix mindegyike legalább αL^{2}-szer előfordul. Hasonlón az M_{g} minden L × 2L méretű részmt́rixában a lehetséges 4 darab 1 × 2-es részmátrix mindegyike legalább αL^{2}- szer előfordul.

Az M_{g} egy A × B részmátrixának x ∈ A sorát B-re nézve α-kiegyensúlyozottnak mondunk, ha a részmátrixon belül az x sorban a nullák aránya 8α és 1 − 8α között van.

(F4) Ha A × B az M_{g} részmátrixa, és |B| ≥ L, akkor A-ban legfeljebb 2L sor nem kiegyensúlyozott B-re nézve (α = 1/32). Ugyanígy ha |A| ≥ L, akkor pedig B-nek lehet csak legfeljebb 2L A-ra nézve kiegyensúlyozatlan oszlopa.

2.24 TÉTEL: Ha g eleget tesz az (F1) feltételnek, akkor a belőle nyert f = f_{g} függvényre C(f) ≥ (2 − o(1)) · n.

Bizonyítás (vázlat): C(f) alulról történő becsléséhez nem használhatjuk az eddig ismert, és alkalmazott technikákat, hiszen olyan f függvényekre, melyek kommunikációs komplexitását a ,,log-rang” illetve a ,,becsapós halmaz” technikával jól lehet alulról becsülni, azokra Tiwari bizonyította a sejtését, így reménytelen, hogy bármelyik módszer működjőn a sejtést cáfoló f-ekre. Tehát mindenképpen egy új becslési technikára van szükség. Az új technika lényege, hogy a függvényre adott tetszőleges protokoll fájában olyan csúcs létezését igazoljuk, melyhez vezető út kellően hosszú, és a csúcsból szintén megfelelően hosszú út található a fa egyik leveléhez. A sok számolást igénylő bizonyítást itt most elhagyjuk, megtalálható [3]-ban.⋄

2.25 TÉTEL: Ha k és n páros, akkor létezik végtelen sok olyan f : {0, 1}^{n} × {0, 1}^{n} ⟶ {0, 1} függvény, amelyre

C_{k}(f) ≤ (\frac{3}{4} + o(1)) · k · C(f).

Bizonyítás: Minden g : \{0, 1\}^{n/2} × \{0, 1\}^{n/2} ⟶ \{0, 1\} függvényre C_{k}(f_{g}) ≤ \frac{3}{4}k · n a 2.22 Tétel értelmében. A 2.24 Tétel pedig biztosítja, hogy majdnem minden g-re C(f_{g}) ≥ (1 − o(1)) · n. E kettőből pedig majdnem minden g-ből kapott f_{g}-re igaz a tétel.⋄

A legjobb, minden f-re igaz eredmény

Láttuk, hogy C_{k}(f) lehet kisebb kC(f)-nél, akár egy 3/4-es szorzóval. Jó lenne viszont azt is tudni, hogy legfeljebb mennyivel lehet kisebb.

Sokáig a legjobb ismert alsó becslés C_{k}(f)-re az alábbi volt:

2.26 TÉTEL: C_{k}(f) = Ω(k · (\sqrt{C(f)} − log k)).

Bizonyítás: Megmutatjuk, hogy R_{0}(f) ≤ \frac{C_{k}(f)}{k} + log k , ahol R_{0}(f) az f randomizált, 0-hibás kommunikációs komplexitása a kétszereplős modellben. Azaz R_{0}(f) az a kommunikációs komplexitás, amit akkor kapunk, ha protokollnak egy a hagyományos módon értelmezett, és az adott függvényt jól kiszámoló protokolokon vett véletlen eloszlást tekintünk, és az így kapott protokoll hosszán a véletlenszerűen választott hagyományos protokoll hosszának a várható értékét értjük. Mivel ismert (ld. pl. [12]), hogy R_{0}(f) = Ω(\sqrt{C(f)}) , így az állítás már következik.

Adott protokollhoz a k hosszú lineáris hálózaton, mely C_{k}(f) kommunikációt használ konstruálunk egy kétszereplős randomizált, 0-hibás protokollt a következőképpen: Az A játékos véletlenszerűen, egyenlő valószínűséggel választ egyet a k kapcsolat közül, mondjuk az l-ediket, és elküldi l-et B-nek (log k bit). Ezek után lefolytatják a hálózat kétszereplős szimulációját az l-edik kapcsolat mentén (2.2 Lemma). E protokoll mellett a kommunikáció várható értéke \frac{C_{k}(f)}{k}. Tehát valóban R_{0}(f) ≤ \frac{C_{k}(f)}{k} + log k. ⋄

Azonban ennél sokkal jobb becslést sikerült adnia M. Dietzfelbingernek [4]-ben. Igazolta, hogy létezik γ konstans, hogy C_{k}(f) ≥ γ · k · C(f). A probléma viszont csak akkor lesz teljesen megoldott, ha sikerül a legnagyobb ilyen γ-t meghatározni, a legjobb eddig ismert érték γ-ra: 0, 275. Nézzünk azonban előbb néhány nagyon fontos lemmát. Szükség lesz a kicserélési lemma (2.10) egy egyszerű, de alapvető fontosságú következményére.

2.27 LEMMA (KÖZREFOGÁSI LEMMA): Ha az (x, y) és (x^{∗}, y^{∗}) inputpárok esetén a P protokoll mellett a kapcsolatokon rendre az (s_{1}, s_{2}, …, s_{k}) illetve a (s_{1}^{∗}, s_{2}^{∗}, …, s_{k}^{∗}) bitsorozatok jelennek meg a kommunikáció során, és az i-edik és j-edik kapcsolaton (1 ≤ i ≤ j ≤ k) egyaránt ugyanaz az s_{i} = s_{i}^{∗} illetve s_{j} = s_{j}^{∗} jön létre, akkor miden köztes kapcsolaton is megegyezik a kommunikáció, azaz s_{l} = s_{l}^{∗} ∀i ≤ l ≤ j.

Bizonyítás: A 2.10 Lemmát először az i-edik kapcsolatra alkalmazva azt kapjuk, hogy (x, y^{∗}) inputra a kapcsolatokon (s_{1}, s_{2}, …, s_{i}^{∗}, s_{i+1}^{∗}, …, s_{k}^{∗}) lesz. Alkalmazva ismét a 2.10 Lemmát, ezúttal a j-edik kapcsolatra, és az (x, y^{∗}), (x, y) inputokra pedig azt adja, hogy az (x, y) esetén meglelenő bitsorozatok: (s_{1}, …, s_{i−1}, s_{i}^{∗}, …, s_{j}^{∗}, s_{j+1}, …, s_{k}) , amiből az egyértelműség miatt (2.1 Lemma) következik a kívánt állítás. ⋄

A most következő lemma kulcsszerepet játszik az alsó becslésben:

2.28 LEMMA: Ha P egy protokoll az f kiszámítására a k hosszú lineáris hálózaton, akkor f-re van kétszereplős protokoll, mely nem több, mint 2^{|P|/⌈k/2⌉} különböző bitsorozatot használ.

Bizonyítás: Legyen k páros az egyszerűség kedvéért. A P indukál egy kétszereplős protokollt (2.2 Lemma) a (k/2)-edik kapcsolat mentén. Tegyük fel, hogy e kétszereplős kommunikáció során t különböző bitsorozat hangozhat el. (Azaz a hálózat k/2-edik kapcsolatán a P protokoll mellett t bitsorozat hangozhat el.) Megmutatjuk, hogy |P| ≥ (k/2)·log t, ami páros k-ra igazolja az állítást. Legyenek (x_{1}, y_{1}), (x_{2}, y_{2}), …, (x_{t}, y_{t}) olyan inputpárok, melyekre a (k/2)-edik kapcsolaton elhangzó bitsorozatok - azaz s_{k/2}(x_{1}, y_{1}), s_{k/2}(x_{2}, y_{2}), …, s_{k/2}(x_{t}, y_{t}) - mind különbözőek. Nyilvánvaló, hogy |P| ≥ \frac{1}{t} · ∑_{j=1}^{t} |s(x_{j}, y_{j})| , ahol s(x_{j}, y_{j}) = s_{1}(x_{j}, y_{j})s_{2}(x_{j}, y_{j}) ⋯ s_{k}(x_{j}, y_{j}) , azaz az összes elhangzott kommunikáció konkatenációja az (x_{j}, y_{j}) input mellett. Ebből

|P| ≥ \frac{1}{t} · ∑_{j=1}^{t} |s_{k/2}(x_{j}, y_{j})| + ∑_{l=1}^{(k/2)−1} \frac{1}{t} ∑_{j=1}^{t} |s_{l}(x_{j}, y_{j})s_{k−l+1}(x_{j}, y_{j})|.

Az s_{k/2}(x_{j}, y_{j}) bitsorozatok egy prefix-mentes halmazt alkotnak, mint azt a 2.3 Lemmában láttuk. Viszont a közrefogási (2.27) lemma miatt az s_{l}(x_{j}, y_{j})s_{k−l+1}(x_{j}, y_{j}) bitsorozatok is mind különböznek, így ezek is egy prefix-mentes halmazt alkotnak. Ezért a 2.4 Lemma mind a k/2 darab átlagértékre alkalmazható, amiből

|P| ≥ log t + ∑_{j=1}^{(k/2)−1} log t = (k/2) · log t.

Ha k páratlan, akkor k/2 helyett mindenhol ⌈k/2⌉ irandó. ⋄

2.29 TÉTEL: Ha f-re létezik kétszereplős protokoll t lehetséges kommunikációs bitsorozattal, akkor C(f) ≤ 2 log_{\frac{3}{2}} t.

Bizonyítás: A feltétel azt jelenti, hogy létezik f-re kétszereplős protokoll, melyhez tartozó protokoll fának t levele van. Elképzelhető azonban, hogy e protokoll fának nagy a mélysége. A C(f) felső becsléséhez e fából egy kiegyensúlyozottabb fával rendelkező protokollt konstruálunk, melynek mélysége legfeljebb 2 log_{\frac{3}{2}} t, ami biztosítja tétel állítását. Egy t levelű bináris fában létezik olyan v pont, hogy t_{v} -a v gyökerű részfa leveinek számateljesíti a t/3 < t_{v} ≤ 2t/3 feltételt. Ilyet találhatunk, ha elindulunk a gyökérből, és mindig abba az irányba megyünk, amelyik gyerekhez tartozó részfának több, mint 2t/3 levele van. Amikor ezt már nem tudjuk megtenni, akkor egy olyan pontban vagyunk, melynek egyik gyereke megfelel v-nek. Jelölje R_{v} azon (x, y) inputpárok halmazát X × Y -ból, melyek eljutnak a v pontba. Tekintsük a következő új protokollt f-re:

Elsőként A és B játékosok eldöntik, hogy a kapott (x, y) inputpár R_{v}-ben ven-e. Ehhez 2 bit kommunikációra van szükség.

(1.) Amennyiben (x, y) ∈ R_{v} , akkor az eredeti protokollt a v pontból folytatják azaz az R_{v}-re megszorított f-re, melyre tehát egy t_{v} levelű protokoll fa áll rendelkezésre.

(2.) Ha (x, y) ∉ R_{v} , akkor akkor az eredeti protokollt használják az f^{∗} : X × Y ⟶ {0, 1} függvényre, ahol f^{∗} = f az R_{v}-n kívül, és f^{∗} = 0 az R_{v}-n. Az f-re vonatkozó protokoll fájában a v gyökerű részfát egy 0-val helyettesítve egy t − t_{v} + 1 levelű protokoll fát kapunk f^{∗}-ra. Nem okoz gondot, hogy a 2. esetben f helyett f^{∗}-ot számolják a játékosok, ugyanis ha (x, y) ∈ R_{v}, akkor nem is ezt az estet alkalmazzuk.

A v megválasztása miatt mindkét esetre kaptunk egy-egy protokollt nem több, mint 2t/3 levéllel. Ha D(t)-vel jelöljük, hogy egy t levelű protokollból ezen algoritmus ismételgetésével mekkora mélységű protokollhoz lehet biztosan eljutni, akkor D(t) ≤ 2 + D(2t/3) kell teljesüljön. Mivel D(1) = 0, így a rekurzív képletből D(t) ≤ 2 log_{\frac{3}{2}} t következik. ⋄

Most már készen állunk, hogy kimondjuk a kívánt tételt:

2.30 TÉTEL: Létezik γ konstans, hogy minden f, k mellett fennáll

C_{k}(f) ≥ γ · k · C(f).

Bizonyítás: A 2.28 Lemmából f-re létezik kétszereplős protokoll, melyhez tartozó protokoll fának legfeljebb 2^{C_{k}(f)/⌈k/2⌉} levele van. Alkalmazva a 2.29 Tételt a C(f) ≤ 2 log_{3/2} (2^{C_{k}(f)/⌈k/2⌉}) eredményre jutunk, amit átalakítva kapjuk, hogy

C_{k}(f) ≥ \frac{1}{2} log \frac{3}{2} · ⌈k/2⌉ · C(f) > γ · k · C(f) ,

ahol γ > 0, 146. ⋄

2.31 MEGJEGYZÉS: E. Kushilevitz rámutatott, hogy a 2.29 Tételbeli becslés javításával akár C(f) ≤ 1, 813 . . . · log t is elérhető, amiből egy erősebb, C_{k}(f) ≥ 0, 275 · k · C(f) becslést kapunk.

3. A ,,homlokra ragasztott szám” modell

A modell

Ebben a modellben, melyet [1] részletesen tárgyal k játékos vesz részt. Mindegyikük saját inputtal rendelkezik, a kommunikáció pedig táblás, azaz egy elhangzott bitről minden játékos tudomást szerez. Van még egy igen speciális tulajdonsága is ennek a modellnek, mégpedig az, hogy a szereplők inputjai között nagy (sőt a lehető legnagyobb) az átfedés. A legjobban úgy fogalmazhatunk, hogy a szereplők mindegyike nem egy-egy inputtal rendelkezik, hanem éppenhogy egy-egy inputtal nem rendelkezik. Azaz minden szereplő birtokában van a k darab inputrészből (k − 1) , és persze mindegyiküktől másik inputrész hiányzik. A modell az elnevezését is e speciális tulajdonságáról kapta, hiszen úgy képzelhetjük el a játékosokat, mintha egy asztal körül ülve mindegyiküknek egy-egy szám lenne ragasztva a homlokára, így valamennyi játékos látná az összes számot, kivéve a saját homlokán lévőt.

Pontosabban megfogalmazva tehát a P_{1}, P_{2}, … P_{k} szereplők kívánják egy adott f : ({0, 1}^{n})^{k} ⟶ {0, 1} függvény f(x_{1}, x_{2}, …, x_{k}) értékét kiszámítani úgy, hogy a P_{i} játékos inputja (x_{1}, x_{2}, …, x_{i−1}, x_{i+1}, … x_{k}) , ahol tehát az x_{j}-k n hosszú 0/1-sorozatok, azaz x_{j} ∈ {0, 1}^{n} : j = 1, 2, …, k.

Ehhez rendelkeznek egy P protokollal, mely megmondja hogy adott pillanatban véget ért-e a kommunikációs folyamat (ez esetben mi az eredmény), és ha nem, akkor melyik játékos következik szólásra, ez (az egyszerre beszélés kizárása érdekében) csak a tábla addigi tartalmától függ. Megmondja továbbá, hogy a soron következő játékos saját inputjának, és a tábla addigi tartalmának függvényében milyen bitet írjon fel a táblára. A kommunikáció hossza a táblára felírt bitek száma. Szokásos módon a protokoll hossza, a különböző inputok mellett a leghosszabb előforduló kommunikáció hossza, és egy függvény kommunikációs komplexitása - melyet e modellben jelöljön C^{k}(f) - pedig a függvényt számoló lehető legrövidebb protokoll hossza.

Cilinder metszetek

E modell legnagyobb előnye, hogy a protokoll fa nagyon hasonlóan viselkedik, mint a kétszereplős esetben. Emlékezzünk vissza, hogy ott egy olyan bináris fáról volt szó, melynek csúcsait A és B betükkel jelöltük meg, aszerint, hogy ki következett szólásra, és a csúcsokból az elküldött bit alapján haladtunk tovább a két lehetséges gyerek valamelyikébe. A különbség itt csak az, hogy a protokoll fa csúcsainak k lehetséges megjelölése lehet, hisz k játékos következhet szólásra. Ebben a ”homlokra ragasztott szám” modellben egy, az 1.4 Tétellel teljesen analóg tétel igaz, azzal a különbséggel, hogy az ottani részmátrixoknak itt cilinder-metszetek felelnek meg.

3.1 DEFINÍCIÓ: Az S_{i} ⊆ X_{1} × X_{2} × ⋯ × X_{k} halmaz cilinder halmaz az i-edik dimenzióban, ha az S_{i}-beliség, mint tulajdonság nem függ az i-edik koordinátától, azaz

(x_{1}, …, x_{i−1}, x_{i}, x_{i+1}, …, x_{k}) ∈ S_{i} ⟺ (x_{1}, …, x_{i−1}, x_{i}^{∗}, x_{i+1}, …, x_{k}) ∈ S_{i}
∀x_{j} ∈ X_{j}(j = 1, …, k) , ∀x_{i}^{∗} ∈ X_{i}

3.2 DEFINÍCIÓ: Az S ⊆ X_{1} × X_{2} × ⋯ × X_{k} halmaz cilinder-metszet, ha előáll S = ⋂_{i=1}^{k} S_{i} alakban, ahol S_{i} halmaz rendre cilinder az i-edik dimenzióban.

A jobb szemléltetés érdekében is hasznos megadni a cilinder-metszetek egy másik, ekvivalens definícióját, amit a szemléltetésen túl sok helyen tudunk majd kíválóan alkalmazni.

3.3 DEFINÍCIÓ: Egy pont k-ast csillagnak nevezünk X_{1} × X_{2} × ⋯ × X_{k}-ban, ha a következő alakú:

(x_{1}^{∗}, x_{2}, …, x_{k}) , (x_{1}, x_{2}^{∗}, …, x_{k}) , …, (x_{1}, x_{2}, …, x_{k}^{∗})

ahol x_{i}, x_{i}^{∗} ∈ X_{i} , és x_{i} ≠ x_{i}^{∗} ∀i ∈ {1, …, k}.

A fenti csillag középpontja (x_{1}, x_{2}, …, x_{k})

3.4 TÉTEL: S cilinder-metszet ⟺ minden C ⊆ S csillag középpontja is S-ben van. Bizonyítás: (⟹) Tegyük fel, hogy S cilinder-metszet az S = ⋂_{i=1}^{k} S_{i} előállítással,

és C = {(x_{1}^{∗}, x_{2}, …, x_{k}) , (x_{1}, x_{2}^{∗}, …, x_{k}) , …, (x_{1}, x_{2}, …, x_{k}^{∗})} egy csillag S-ben. Akkor minden i mellett teljesül (x_{1}, …, x_{i}^{∗}, …, x_{k}) ∈ S ⊆ S_{i} ⟹ (x_{1}, …, x_{i}, …, x_{k}) ∈ S_{i} , hiszen S_{i} cilinder az i-edik dimenzióban. Mivel (x_{1}, …, x_{i}, …, x_{k}) ∈ S_{i} ∀i = 1, 2, …, k ebből (x_{1}, …, x_{i}, …, x_{k}) ∈ S , tehát a csillag középpontja is S-ben van.

(⟸) Legyen az S olyan, hogy minden S-beli csillag középpontja is S-ben van. Az

S_{i} := {(x_{1}, …, x_{i}, …, x_{k}) ∈ X_{1}×X_{2}×⋯×X_{k} | ∃x_{i}^{∗} ∈ X_{i} : (x_{1}, …, x_{i}^{∗}, …, x_{k}) ∈ S} jelölés mellett (i = 1, 2, …, k) nyilvánvaló, hogy S_{i} halmaz cilinder az i-edik dimenzióban. Meg kell még mutatnunk, hogy S = ⋂_{i=1}^{k} S_{i} . Az S_{i}-k definíciójából világos, hogy S ⊆ S_{i} ∀i ⟹ S ⊆ ⋂_{i=1}^{k} S_{i} . Az S ⊇ ⋂_{i=1}^{k} S_{i} irányú tartalmazás pedig abból következik, hogy amennyiben (x_{1}, …, x_{i}, …, x_{k}) ∈ ⋂_{i=1}^{k} S_{i} , akkor ∀i-re ∃x_{i}^{∗} , hogy (x_{1}, …, x_{i}^{∗}, …, x_{k}) ∈ S . Ezek az Sbeli elemek egy csillagot alkotnak, melynek középpontja, azaz (x_{1}, …, x_{i}, …, x_{k}) a feltétel szerint ugyancsak S-ben kell legyen. ⋄

Jelöljük R_{ℓ}-lel azon inputok halmazát az X_{1} × X_{2} × ⋯ × X_{k}-ból, melyek mellett az ℓ levélbe jutunk a protokoll fában.

3.5 TÉTEL: A protokoll fa mindel ℓ levelére az R_{ℓ} halmaz egy monokromatikus cilinder-metszet.

Bizonyítás: Hogy R_{ℓ} monokromatikus, az nyilvánvaló. Az 1.4 Tétel bizonyításához hasonlóan teljes indukcióval megmutatható, hogy a protokoll fa minden v pontjára az inputok azon R_{v} halmaza, melyek elérik a v pontot cilinder-metszetet alkotnak. Azonban a 3.4 Tétel által adott ekvivalens definíciót használva a cilinder-metszetre egy mégegyszerűbb bizonyítást adhatunk:

Megmutatjuk, hogy minden R_{ℓ}-beli csillag középpontja is ott van. Ez igaz hiszen ha (x_{1}^{∗}, x_{2}, …, x_{k}) , (x_{1}, x_{2}^{∗}, …, x_{k}) , …, (x_{1}, x_{2}, …, x_{k}^{∗}) ∈ R_{ℓ} , akkor ezen inputok mind az ℓ levélbe vezetnek. Viszont amikor P_{i} játékos (i = 1, 2, …, k) mond egy bitet, akkor ő nem tud különbséget tenni az (x_{1}, …, x_{i}^{∗}, …, x_{k}) és (x_{1}, …, x_{i}, …, x_{k}) inputok között, így a kommunikáció az (x_{1}, …, x_{i}, …, x_{k}) input esetén is az ℓ levélbe jut. ⋄

3.6 KÖVETKEZMÉNY: Egy t bit hosszúságú protokoll az X_{1} × X_{2} × ⋯ × X_{k} inputhalmazt legfeljebb 2^{t} darab monokromatikus cilinder-metszetre osztja.

Becslések diszkrepanciával

Általában a kétszereplős kommunikációs komplexitásra vonatkozó alsó becslések nem működnek a többszereplős modellben. Az egyetlen módszer, amely egy az egyben átvihető az a diszkrepancia módszer. E módszer jól használható a kétszereplős modellben az ε-hibás kommunikációs komplexitás, és ezáltal a kommunikációs komplexitás alsó becslésére is.

3.7 DEFINÍCIÓ: Azt mondjuk, hogy egy P protokoll ε hibával kiszámolja az f függvényt a kétszereplős modellben (0 ≤ ε ≤ 1/2), ha P r(P (x, y) = f(x, y)) ≥ 1 − ε , ahol P (x, y)-nal azt az eredményt jelöljük, amit a P protokoll számol az (x, y) inputra. A valószínűséget itt úgy kell érteni, hogy a lehetséges (x, y) ∈ X × Y inputok egyenlő valószínűséggel léphetnek fel. Tehát a protokoll egy 1/2-nél nagyobb, de nem feltétlenül 1 valószínűséggel adja a helyes eredményt egy (x, y) véletlenszerűen választott inputon. Jelöljük C_{ε}(f)-fel a legrövidebb, f-et ε hibával számoló protokoll hosszát. Megjegyzendő, hogy eredetileg ezt a jelölést olyan esetben alkalmazzák, amikor a protokoll véletlent (pl. pénzfeldobásokat) is használhat. A tételek, melyeket igazolunk erre az esetre is igazak, de nincs szükség e fejezetben a véletlen használatára, így a definíciót e nélkül mondtuk ki.

Ha M az M_{f} mátrix egy részmátrixa, akkor

Disc(f, M) := |P r[f(x, y) = 0, (x, y) ∈ M] − [P r[f(x, y) = 1, (x, y) ∈ M]|,

ahol a valószínűséget az inputok egyenletes eloszlása mellett kell érteni. A diszkrepanciát a kétszereplős modellben egy adott f függvényre a következőképpen definiáljuk:

Disc(f) := max_{M} Disc(f, M),

ahol M végigfut az M_{f} összes részmátrixán.

A diszkrepanciát természetesen nem csak egyenletes inputeloszlás mellett lehet értelmezni, de itt nekünk csak arra lesz szüksëgünk.

3.8 TÉTEL: Minden f : X × Y ⟶ {0, 1} függvény, és 0 ≤ ε ≤ 1/2 mellett igaz, hogy C_{\frac{1}{2} −ε}(f) ≥ log \frac{2ε}{Disc(f)} .

Bizonyítás: Amennyiben P egy t bitet használó protokoll az f-re, amely legalább \frac{1}{2} + ε valószínűséggel ad helyes eredményt, akkor

\begin{aligned}2ε & ≤ P r[P (x, y) = f(x, y)] − P r[P (x, y) ≠ f(x, y)] = \\ & = ∑_{ℓ}(P r[P (x, y) = f(x, y) és (x, y) ∈ R_{ℓ}] − P r[P (x, y) ≠ f(x, y) és (x, y) ∈ R_{ℓ}]) \end{aligned}

ahol a szummázás a protokoll fa összes levelére történik. Mivel az R_{ℓ} halmazok P -re nézve monokromatikusak, így a kifejezés tovább becsülhető felülről azzal, hogy:

∑_{ℓ} |P r[f(x, y) = 0 és (x, y) ∈ R_{ℓ}] − P r[f(x, y) = 1 és (x, y) ∈ R_{ℓ}]| .

Mivel minden R_{ℓ} egy-egy részmátrixa M_{f}-nek, így a szumma minden egyes tagját felülről becsli a Disc(f). A szummának pedig legfeljebb 2^{t} tagja lehet, hiszen legfeljebb ennyi levéllel rendelkezhet egy t mélységű bináris fa. Tehát azt kaptuk, hogy 2ε ≤ 2^{t}Disc(f) , amiből átrendezéssel a kívánt t ≥ log (\frac{2ε}{Disc(f)}) egyenlőtlenség adódik. ⋄

3.9 KÖVETKEZMÉNY: C(f) ≥ log \frac{1}{Disc(f)}

Nézzük hogyan vihető át ez a tétel a ,,homlokra ragasztott szám” modellre. Ebben a többszereplős modellben a diszkrepanciát a következőképpen definiálhatjuk:

3.10 DEFINÍCIÓ: Ha f : X_{1} × X_{2} × ⋯ × X_{k} ⟶ {0, 1} függvény, S pedig egy cilinder-metszet X_{1} × X_{2} × ⋯ × X_{k}-ben, akkor

Disc(f, S) := |P r[f(x_{1}, x_{2}, …, x_{k}) = 0, (x, y) ∈ S] − [P r[f(x_{1}, x_{2}, …, x_{k}) = 1, (x, y) ∈ S]|

Disc(f) := max_{S} Disc(f, S) ,

ahol a maximumot az összes cilinder-metszet felett vesszük.

A kétszereplős esettel analóg módon definálható k szereplő esetén az ε-hibás kommunikációs komplexitás (C_{ε}^{k}), melyre akárcsak ott is igaz a következő tétel.

3.11 TÉTEL: C_{\frac{1}{2} −ε}^{k}(f) ≥ log \frac{2ε}{Disc(f)} .

Bizonyítás: A 3.8 Tétel bizonyítása egy az egyben átvihető a többszereplős esetre.⋄

3.12 KÖVETKEZMÉNY: C^{k}(f) ≥ log \frac{1}{Disc(f)}

E következmény felhasználásával a diszkrepancia felső becslésével a kommunikációs komplexitást alulról tudjuk becsülni. Nézzük ezt meg az általánosított belső szorzat (a GIP) függvény esetében.

3.13 DEFINÍCIÓ: Ha x_{1}, x_{2}, …, x_{k} ∈ {0, 1}^{n}, akkor az általánosított belső szorzat függvényt úgy definiáljuk, hogy GIP_{n}^{k}(x_{1}, x_{2}, …, x_{k}) = 1 pontosan akkor, ha páratlan azon 1 ≤ j ≤ n indexek száma, melyekre valamennyi x_{i} j-edik bitje 1.

E függvény kommunikációs komplexitására először Babai, Nisan és Szegedy adott alsó becslést [5]-ben:

3.14 TÉTEL: C^{k}(GIP_{n}^{k}) = Ω(\frac{n}{4^{k}})

Bizonyítás: A 3.12 Következmény értelmében elég megmutatnunk, hogy

Disc(GIP_{n}^{k}) ≤ e^{−( \frac{n}{4^{k}} )}.

Az egyszerűbb algebrai kezelhetőség érdekében vezessük be a következő f függvényt:

f(x_{1}, …, x_{k}) := \{ \begin{matrix}+1 & ha GIP_{n}^{k}(x_{1}, …, x_{k}) = 0 \\ −1 & ha GIP_{n}^{k}(x_{1}, …, x_{k}) = 1 \end{matrix}

Jelölje

Δ_{k}(n) = max_{ϕ_{1},...,ϕ_{k}} |E_{x_{1},...,x_{k}}[f(x_{1}, …, x_{k}) · ϕ_{1}(x_{1}, …, x_{k}) ⋯ ϕ_{k}(x_{1}, …, x_{k})]| ,

ahol a maximumot az összes olyan ϕ_{1}, …, ϕ_{k} függvénysorozat felett vesszük, ahol ϕ_{i} : ({0, 1}^{n})^{k} ⟶ {0, 1} függvény nem függ az x_{i} változótól, az E_{x_{1},...,x_{k}} pedig várható értéket jelöl az inputok egyenlő valószínéggel történő választása mellett. Vegyük észre, hogy Disc(GIP_{n}^{k}) = Δ_{k}(n), ugyanis azon pontok halmaza az X_{1} × ⋯ × X_{k} inputtérből, melyekre ϕ_{1}(x_{1}, …, x_{k}) ⋯ ϕ_{k}(x_{1}, …, x_{k}) érték 1-et ad egy cilinder metszetet alkot, és minden cilinder-metszet felírható egy ilyen szorzattal. Továbbá mivel áttértünk a {−1, +1} értékekre, ezért itt a várható érték megegyezik a valószínűségek különbségével a diszkrepancia definíciójában.

Definiáljuk rekurzív módon a következő számsorozatot: β_{1} := 0, és β_{j} := \sqrt{\frac{1+β_{j−1}}{2}} .

Indukcióval könnyen kijön, hogy β_{k} ≤ 1 − 4^{1−k} < e^{−4^{1−k}} , ezért azt kell igazolnunk, hogy

Δ_{k}(n) ≤ (β_{k})^{n} .

Ezt k-ra vonatkozó teljes indukcióval fogjuk megtenni. Nyilván Δ_{1}(n) = 0 = β_{1} , hiszen ekkor ϕ_{1} konstans, ezáltal Δ_{1}(n) = E_{x_{1}}[f(x_{1})] = 0 . Tegyük fel, hogy k ≥ 2, és k-nál kisebb értékekre tudjuk, hogy igaz az állítás. Legyenek ϕ_{1}, …, ϕ_{k} olyan függvények, melyek mellet Δ_{k}(n) felveszi az értékét. Mivel ϕ_{k} függvény nem függ az x_{k} változótól, és abszolút értékét felülről becsülhetjük 1-gyel, így

Δ_{k}(n) ≤ E_{x_{1},...,x_{k−1}}[|E_{x_{k}}[f(x_{1}, …, x_{k}) · ϕ_{1}(x_{1}, …, x_{k}) ⋯ ϕ_{k−1}(x_{1}, …, x_{k})]|] .

Felhasználva a Cauchy-Schwartz egyenlőtlenség egy speciáciális esetét, azaz, hogy egy z valószínűségi változóra (E[z])^{2} ≤ E[z^{2}] azt kapjuk, hogy

Δ_{k}(n) ≤ (E_{x_{1},...,x_{k−1}}[E_{x_{k}}[f(x_{1}, …, x_{k}) · ϕ_{1}(x_{1}, …, x_{k}) ⋯ ϕ_{k−1}(x_{1}, …, x_{k})]]^{2})^{1/2} =

= (E_{u,v,x_{1},...,x_{k−1}}[f(x_{1}, …, x_{k−1}, u) · f(x_{1}, …, x_{k−1}, v) · ϕ_{1}^{u} · ϕ_{1}^{v} ⋯ ϕ_{k−1}^{u} · ϕ_{k−1}^{v}])^{1/2} ,

ahol ϕ_{i}^{u} = ϕ_{i}(x_{1}, …, x_{k−1}, u) és ϕ_{i}^{v} = ϕ_{i}(x_{1}, …, x_{k−1}, v) .

Az x_{i} ∈ {0, 1}^{n} vektorokat tekinthetjük egy n elemű X halmaz egy-egy részhalmazának a karakterisztikus vektorának, azaz az x_{i} vektort azonosíthatjuk a neki megfelelő részhalmazzal. Vegyük észre, hogy ekkor f(x_{1}, …, x_{k}) = (−1)^{| ⋂_{i=1}^{k} x_{i}|} , ahol a jobb oldalon lévő x_{i}-k már mint halmazok értendők. Ebből u△v-vel jelölve az u és v halmazok szimmetrikus differenciáját az adódik, hogy

\begin{aligned}f(x_{1}, …, x_{k−1}, u) · f(x_{1}, …, x_{k−1}, v) & = (−1)^{|u∩⋂_{i=1}^{k−1} x_{i}|+|v∩⋂_{i=1}^{k−1} x_{i}|} = \\ & = (−1)^{|(u△v)∩⋂_{i=1}^{k−1} x_{i}|} = (−1)^{⋂ z_{i}} = f(z_{1}, …, z_{k−1}) \end{aligned}

ahol z_{i} = x_{i} ∩ (u△v) , azaz minden x_{i} vektor két részre, y_{i}-re és z_{i}-re osztható, ahol z_{i} az x_{i} azon j-edik koordinátáiból áll, amelyekre u_{j} ≠ v_{j}. Itt kihasználtuk, hogy azon elemek, melyek u-ban és v-ben (mint részhalmazban) egyaránt benne vannak, illetve amelyek egyikben sincsenek benne, azok a (−1) kitevőjében páros sokszor szerepelnek, így nyugodtan elhagyhatók. Akkor tehát

Δ_{k}(n) ≤ (E_{u,v,y_{1},...,y_{k−1}}[E_{z_{1},...z_{k−1}}[f(z_{1}, …, z_{k−1}) · ϕ_{1}^{u}ϕ_{1}^{v} ⋯ ϕ_{k−1}^{u}ϕ_{k−1}^{v}]])^{1/2} .

A z_{i}-k, mint láttuk |u△v| hosszú vektorok, a ϕ_{i}^{u} · ϕ_{i}^{v} szorzatfüggvény pedig tekinthető a (z_{1}, z_{2}, …, z_{k−1}) változókon értelmezett függvénynek, amely viszont nem függ a z_{i} változótól, így az indukciós feltevés miatt

E_{z_{1},...z_{k−1}}[f(z_{1}, …, z_{k−1}) · ϕ_{1}^{u}ϕ_{1}^{v} ⋯ ϕ_{k−1}^{u}ϕ_{k−1}^{v}] ≤ Δ_{k−1}(|u△v|) ≤ (β_{k−1})^{|u△v|} .

Tehát azt kaptuk, hogy

Δ_{k}(n) ≤ (E_{u,v,y_{1},...,y_{k−1}}[β_{k−1}^{|u△v|}])^{1/2} = (E_{u,v}[β_{k−1}^{|u△v|}])^{1/2} .

Amennyiben u és v uniform módon választott véletlen vektorok a {0, 1}^{n}-ből, akkor az u △ v vektor (illetve halmaz) eloszlása is egyenletes, tehát P r(|u△v| = m) = \binom{n}{m}2^{−n} . Ezért a becslés így folytatható tovább:

Δ_{k}(n) ≤ [ ∑_{m=0}^{n} \binom{n}{m}2^{−n}β_{k−1}^{m}]^{1/2} = [2^{−n}(1 + β_{k−1})^{n}]^{1/2} = (β_{k})^{n} .⋄

3.15 MEGJEGYZÉS: Ez a becslés tovább javítható, ugyanis, mint azt Chung és Tetali [8]-ban megmutatta GIP_{n}^{k} = Ω(\frac{n}{2^{k}}). Bizonyításuk a kvázi-random gráfok elméletén alapul.

Ebben a modellben valamennyi ismert alsó becslés, akárcsak ez is a k növelésével exponenciálisan csökken. Jó lenne olyan függvényt találni, melyre k-tól legalább nem exponenciálisan függő, például \frac{n}{k^{c}} típusú alsó becslés adható. Az előbb látott GIP függvény biztosan nem ilyen, ugyanis Grolmusz Vince [10]-ben igazolta, hogy az \frac{n}{2^{k}} alsó becslés már éles.

3.16 TÉTEL: GIP_{n}^{k} = O(k \frac{n}{2^{k}})

Bizonyítás: Célszerű az inputokat egy k×n-es A mátrixként tekinteni, melynek tehát i-edik sora az x_{i} inputrész. A GIP_{n}^{k} függvény az A mátrix csupa 1-esekből álló oszlopai számának paritását adja meg. Tekintsük a következő protokollt ennek kiszámítására.

Bontsuk fel az A mátrixot 2^{k−1} − 1 oszlopból álló blokkokra, persze az utolsó blokkba a maradék oszlopok kerülnek, melyek száma lehet ennél kisebb. Vegyük észre, hogy ha a GIP_{n}^{k} értékét ezekre a blokkokra kiszámítjuk , akkor ezeket az értékeket már csak összegezni kell modulo 2. Nézzük, hogyan számolhatjuk ki egy adott blokkra a GIP_{n}^{k} értékét nem több, mint 2k bit kommunikációval:

Először P_{1}, az első játékos kijelent egy olyan α vektort, amely nem szerepel az adott blokk oszlopai között. Ugyan nem ismeri az első sort, mégis tud ilyet mondani, hiszen a legfeljebb 2^{k−1} − 1 oszlop mindegyikének csak az első koordinátáját nem ismeri, így azok helyére mindkét lehetséges bitet beírva is csak 2^{k} − 2 oszlop jöhet számításba, viszont összesen 2^{k} féle oszlopvektor létezik.

Amennyiben α = (1, 1, …, 1) , akkor e blokkra a GIP_{n}^{k} értéke biztosan 0, és nincs is szükség további kommunikációra. Ha nem, akkor az α vektornak létezik 0 koordinátája. Feltehetjük, hogy α = (0, …, 0, 1, …, 1) alakú, ahol l darab 0 után k − l darab 1-es következik, ugyanis ellenkező esetben a játékosok átpermutálhatók úgy, hogy ilyen alakúvá váljon. Jelölje y_{i} (i = 0, 1, 2, …, k) a blokkban szereplő (0, …, 0, 1, …, 1) alakú oszlopok számát mod 2, ahol i darab 0 után jön k − i darab 1-es, z_{i} pedig (i = 1, 2, …, k) a blokkban szereplő (0, …, 0, ∗, 1, …, 1) alakú oszlopok számát mod 2, ahol i − 1 darab 0-t egy tetszőleges bit követ az i-edik pozícióban, majd n − i darab 1-es következik. Most minden i-re P_{i} bejelenti a z_{i} értékét, amit nyilván meg tud állapítani a saját inputjából. Mivel z_{i} = y_{i} + y_{i−1} , és y_{l} = 0 ismert, mert α nem fordul elő az oszlopok között, így a z_{i}-kből kiszámítható y_{0}, ami nem más, mint a GIP_{n}^{k}-nak erre a blokkra megszorított értéke. Méghozzá

y_{0} = y_{0} + y_{l} = ⨁_{i=1}^{l} z_{i} .

(A ⊕ mod 2 összeadást jelent.)

Az α bejelentése k bitet igényel, míg a z_{i}-k közlése további k bit. Mivel a blokkok száma O(\frac{n}{2^{k}}), és minden blokkra elég 2k bit kommunikáció, így e protokoll valóban O(k \frac{n}{2^{k}}) kommunikációval számolja GIP_{n}^{k} értékét. ⋄

A kocka-módszer

Ez a módszer valójában még a diszkrepanciát használó alsó becslési módszerek közé tartozik. Ran Raz [9] felfedezett egy olyan, függvényekhez rendelhető mennyiséget, amely a diszkrepanciát felülről becsli, viszont kiszámítása sokkal egyszerűbb. Tulajdonképpen a 3.14 Tétel bizonyításának egy általánosításáról van szó, melyet ha elvégzünk, akkor sok függvényre a számolás jelentősen csökkenthető.

3.17 DEFINÍCIÓ: Az X̄ = X_{1} × X_{2} × ⋯ × X_{k} inputtérben kockának nevezünk egy D = {a_{1}, b_{1}} × {a_{2}, b_{2}} × ⋯ × {a_{k}, b_{k}} alakú részhalmazt, ahol ∀i : a_{i}, b_{i} ∈ X_{i} (nem feltétlenül különbözőek). Jelölje D az összes kockák halmazát.

3.18 DEFINÍCIÓ: Egy D ∈ D kocka (f-re vonatkozó) előjele legyen

S_{f}(D) := ∏_{d_{1}∈{a_{1},b_{1}}} ∏_{d_{2}∈{a_{2},b_{2}}} ⋯ ∏_{d_{k}∈{a_{k},b_{k}}} f(d_{1}, …, d_{k}),

ahol az f a {−1, +1}-be képező függvény. A {0, 1}-be képező Boole-függvényeket ezért előbb át kell alakítani ilyenné, mint azt a 3.14 Tétel bizonyításában is tettük. Látható, hogy az S_{f} : D ⟶ {−1, +1} függvény pontosan akkor ad +1 értéket, amennyiben a D kockán az f páros sok helyen vesz fel −1-et (és ekkor 1-et is).

3.19 DEFINÍCIÓ: Jelölje E(f) := E_{D}[S_{f}(D)], ahol a várható értéket a D uniform megválasztása mellet tekitjük (ez persze ekvivalens azzal, hogy az a_{i}, b_{i} elemeket uniform módon választjuk az X_{i}-ből minden i = 1, 2, …, k mellett).

Ennek az E(f)-nek az \frac{1}{2^{k}} -adik hatványa lesz az a mennyiség, ami felülről becsli a diszkrepanciát. Ezt majd a 3.22 Tételben fogjuk látni.

3.20 LEMMA: Jelölje egy h : X̄ ⟶ {−1, +1} függvényre Δ(h) := E_{x̄∈X̄}[h(x̄)], ahol a várható értéket az egyenletes eloszlás szerint vesszük. Akkor

E(h) ≥ |Δ(h)|^{2^{k}}.

Bizonyítás:

E(h) = E_{D}[S_{h}(D)] = E_{a_{1},b_{1}∈X_{1}} ⋯ E_{a_{k},b_{k}∈X_{k}} ∏_{d_{1}∈{a_{1},b_{1}}} ⋯ ∏_{d_{k}∈{a_{k},b_{k}}} h(d_{1}, …, d_{k}).

Tetszőleges X_{k}-n értelmezett g függvényre fennáll

E_{a_{k},b_{k}∈X_{k}}[g(a_{k})g(b_{k})] = (E_{x_{k}∈X_{k}}[g(x_{k})])^{2}.

Rögzített a_{1}, b_{1}, …, a_{k−1}, b_{k−1} mellett legyen most

g(x_{k}) = ∏_{d_{1}∈{a_{1},b_{1}}} ⋯ ∏_{d_{k−1}∈{a_{k−1},b_{k−1}}} h(d_{1}, …, d_{k−1}, x_{k}).

Ezáltal

E(h) = E_{a_{1},b_{1}∈X_{1}} ⋯ E_{a_{k−1},b_{k−1}∈X_{k−1}}(E_{x_{k}} ∏_{d_{1}∈{a_{1},b_{1}}} ⋯ ∏_{d_{k−1}∈{a_{k−1},b_{k−1}}} h(d_{1}, …, d_{k−1}, x_{k}))^{2}.

Alkalmazva a Cauchy-Schwartz egyenlőtlenséget, mely szerint egy z valószínűségi változóra E[z^{2}] ≥ (E[z])^{2}, az következik, hogy

E(h) ≥ (E_{a_{1},b_{1}∈X_{1}} ⋯ E_{a_{k−1},b_{k−1}∈X_{k−1}}E_{x_{k}} ∏_{d_{1}∈{a_{1},b_{1}}} ⋯ ∏_{d_{k−1}∈{a_{k−1},b_{k−1}}} h(d_{1}, …, d_{k−1}, x_{k}))^{2}

= (E_{x_{k}}E_{a_{1},b_{1}∈X_{1}} ⋯ E_{a_{k−1},b_{k−1}∈X_{k−1}} ∏_{d_{1}∈{a_{1},b_{1}}} ⋯ ∏_{d_{k−1}∈{a_{k−1},b_{k−1}}} h(d_{1}, …, d_{k−1}, x_{k}))^{2}.

Ezt k-szor ismételve pedig azt kapjuk, hogy

E(h) ≥ (E_{x_{k}∈X_{k}} ⋯ E_{x_{1}∈X_{1}}h(x_{1}, …, x_{k}))^{2^{k}} = |Δ(h)|^{2^{k}}.⋄

3.21 LEMMA: Tetszőleges f : X̄ ⟶ {−1, +1} függvényhez létezik egy olyan h : X̄ ⟶ {−1, +1} függvény, amelyre E(h) = E(f), és |Δ(h)| ≥ Disc(f).

Bizonyítás: Azt fogjuk használni, hogy amennyiben tetszőleges i ∈ {1, 2, …, k} mellett g nem függ az i-edik változójától, akkor E(fg) = E(f) (itt fg(x) = f(x)g(x) a szorzatfüggvényt jelöli). Ez ∀ f, g mellett igaz, hiszen nyilván minden D kockára a definíció szerint S_{fg}(D) = S_{f}(D)S_{g}(D), és ha g nem függ például az x_{k} változótól, akkor g(d_{1}, …, d_{k−1}, a_{k}) = g(d_{1}, …, d_{k−1}, b_{k}) ∀d_{1}, …, d_{k}, a_{k}, b_{k} mellett, így a g függvény páros sok D-beli elemen ad 1-et, tehát S_{g}(D) = 1. Ebből az is következik, hogy ha g_{i} nem függ az i-edik változójától, akkor

E(fg_{1}g_{2} ⋯ g_{k}) = E(f).

Jelöljön most T = ⋂_{i=1}^{k} T_{i} egy olyan cilinder-metszetet, melyre Disc(f, T) = Disc(f). Legyen i ∈ {1, 2, …, k} esetén g_{i} : X̄ ⟶ {−1, +1} a következő függvény (valószínűségi változó): g_{i}(x̄) = 1 (1 valószínűséggel) ha x̄ ∈ T_{i}, ellenkező esetben pedig \frac{1}{2} valószínűséggel g_{i}(x̄) = 1 illetve \frac{1}{2} valószínűséggel g_{i}(x̄) = −1. A g_{i}-k legyenek persze függetlenek. Jelölje továbbá g := g_{1}g_{2} ⋯ g_{k}. Akkor az előbb említettek miatt teljesül

E(fg) = E(f).

Vegyük észre, hogy amennyiben x̄ ∈ T, akkor (1 valószínűséggel) g(x̄) = 1, különben pedig \frac{1}{2} valószínűséggel g(x̄) = 1, és \frac{1}{2} valószínűséggel g(x̄) = −1. Ezért ha x̄ ∈ T, akkor E_{g}[g(x̄)] = 1 ha pedig x̄ ∉ T, akkor E_{g}[g(x̄)] = 0. Azaz E_{g} éppen a T halmaz karakterisztikus függvénye. Ezáltal

|E_{g}Δ(fg)| = |E_{g}Ex̄[f(x̄)g(x̄)]| = |Ex̄E_{g}[f(x̄)g(x̄)]| = |Ex̄[f(x̄)E_{g}[g(x̄)]]| =
= ||{x̄ : x̄ ∈ T, f(x̄) = 1}| − |{x̄ : x̄ ∈ T, f(x̄ = −1)}|| = Disc(f, T).

A konvexitás miatt pedig

E_{g}|Δ(fg)| ≥ |E_{g}Δ(fg)| = Disc(f, T) = Disc(f).

Tehát létezik olyan g, hogy a h = fg választás mellett teljesülnek a kívánt feltételek.⋄

3.22 TÉTEL: ∀f : X̄ ⟶ {−1, +1} függvényre E(f) ≥ Disc(f)^{2^{k}}. Bizonyítás: A 3.21 Lemmából nyert h-ra alkalmazva a 3.20 Lemmát

E(f) = E(h) ≥ |Δ(h)|^{2^{k}} ≥ Disc(f)^{2^{k}}.⋄

3.23 KÖVETKEZMÉNY: C^{k}(f) ≥ 2^{−k} log \frac{1}{E(f)}.

Bizonyítás: A 3.12 Következmény és a 3.22 Tétel következménye.⋄

Hogy eddig eljussunk sokat kellett számolnunk, de megérte, ugyanis sok f-re az E(f) pontos értéke könnyen, kombinatorikai eszközökkel számolható. Nézzük meg például a GIP függvényhez tartozó E értéket.

3.24 ÁLLÍTÁS: E(f) = (1− \frac{1}{2^{k−1}} )^{n}, ahol f a GIP_{n}^{k} függvény \{−1, +1\} értékkészletű változata.

Bizonyítás: Legyen D = {a_{1}, b_{1}} × {a_{2}, b_{2}} × ⋯ × {a_{k}, b_{k}} egy tetszőleges kocka ({0, 1}^{n})^{k}-ban. Mint azt a 3.14 Tétel bizonyításában már láttuk, ez a függvény tulajdonképpen egy n elemű alaphalmaz részhalmazaira megadja a metszet paritását. Jelöljük ezért a kisbetűs 0/1 sorozatoknak megfeleltethető részhalmazt a megfelelő nagybetűvel. Akkor

S_{f}(D) = ∏_{{d_{i}∈\{a_{i},b_{i}\} \atop i∈\{1,2,...,k\}}} f(d_{1}, …, d_{k}) = ∏_{{D_{i}∈\{A_{i},B_{i}\} \atop i∈\{1,2,...,k\}}}(−1)^{|⋂_{i=1}^{k} D_{i}|} = (−1)^{∑_{{D_{i}∈\{A_{i},B_{i}\} \atop i∈\{1,2,...,k\}}} |⋂_{i=1}^{k} D_{i}|}.

Ebből pedig

S_{f}(D) = (−1)^{|⋂_{i=1}^{k} A_{i}△B_{i}|},

hiszen azon elemek, melyek nem A_{i} △B_{i}-ben vannak biztosan páros sokszor adódnak össze a (−1) kitevőjében.

A D kocka véletlen megválasztása ekvivalens az A_{i}, B_{i} halmazok uniform módon történő megválasztásával. Ekkor pedig az A_{i} △ B_{i} halmaz is az egyenletes eloszlás szerint választódik ki, azaz minden alaphalmazbeli elem 1/2 valószínűséggel van A_{i} △ B_{i}-ben. Ebből

E(f) = E_{D}[S_{f}(D)] = ∑_{j=1}^{n}(−1)^{j} · p_{j},

ahol p_{j} annak a valószínűsége, hogy az n elemű alaphalmaz k darab véletlenszerűen választott részhalmazának metszete j elemű. Tehát

p_{j} = \binom{n}{j}(\frac{1}{2^{k}} )^{j}(1 − \frac{1}{2^{k}} )^{n−j}

És így

E(f) = ∑_{j=1}^{n}(−1)^{j}\binom{n}{j}(\frac{1}{2^{k}} )^{j}(1 − \frac{1}{2^{k}} )^{n−j} = ((1 − \frac{1}{2^{k}} ) − \frac{1}{2^{k}} )^{n} = (1 − \frac{1}{2^{k−1}} )^{n}. ⋄

Ebből pedig a 3.23 Következménnyel ismét adódik a 3.14 Tétel.

Nézzünk meg a kocka módszert egy másik függvény esetén is. Jelölje X = {0, 1}^{n×n} az n × n-es 0/1 mátrixok halmazát. Ha x_{1}, x_{2}, …, x_{k} ∈ X, akkor az F, mátrix szorzás függvényt a következőképpen értelmezzük:

F (x_{1}, x_{2}, …, x_{k}) = (x_{1} · x_{2} ⋯ x_{k})_{1,1}.

Tehát F (x_{1}, x_{2}, …, x_{k}) az x_{1}, x_{2}, …, x_{k} mátrixok (GF (2) felett tekintett) szorzatának bal felső sarkában lévő eleme. Térjünk át ismét {−1, +1} értékkészletre, azaz legyen f(x_{1}, x_{2}, …, x_{k}) := (−1)^{F (x_{1},x_{2},...,x_{k})}.

3.25 ÁLLÍTÁS: Erre az f-re E(f) ≤ \frac{k−1}{2^{n}}.

Bizonyítás: Legyen D = {a_{1}, b_{1}} × {a_{2}, b_{2}} × ⋯ × {a_{k}, b_{k}} egy tetszőleges kocka X^{k}-ban. Akkor

S_{f}(D) = ∏_{{d_{i}∈\{a_{i},b_{i}\} \atop i∈\{1,2,...,k\}}} f(d_{1}, …, d_{k}) = ∏_{{d_{i}∈\{a_{i},b_{i}\} \atop i∈\{1,2,...,k\}}}(−1)^{F (d_{1},d_{2},...,d_{k})} = (−1)^{∑_{{d_{i}∈\{a_{i},b_{i}\} \atop i∈\{1,2,...,k\}}} F (d_{1},d_{2},...,d_{k})}

Az utóbbi összegzés nyilván elég, ha GF (2) felett történik. Mivel F minden változójában lineáris, így ha ⊕ jelöli a GF (2) feletti összeadást, akkor

S_{f}(D) = (−1)^{F (a_{1}⊕b_{1},a_{2}⊕b_{2},...,a_{k}⊕b_{k})}

Ha a D kocka uniform módon választott, akkor (a_{1} ⊕ b_{1}, a_{2} ⊕ b_{2}, …, a_{k} ⊕ b_{k}) is egyenletes eloszlással van választva X^{k}-ból, ezért

E(f) = E_{D}[S_{f}(D)] = E_{D}[(−1)^{F (a_{1}⊕b_{1},a_{2}⊕b_{2},...,a_{k}⊕b_{k})}] =
= Ex⃗[(−1)^{F (x_{1},x_{2},...,x_{k})}] = Ex⃗[f(x_{1}, x_{2}, …, x_{k})] =: Δ(f)

A Δ(f) becsléséhez legyen (x_{1}, x_{2}, …, x_{k}) véletlen vektor egyenletes eloszlással véve az X^{k}-ból. Jelölje E_{d} (1 ≤ d ≤ k esetén) azt az eseményt, hogy az x_{1} · x_{2} ⋯ x_{d} mátrix első sorának minden eleme 0. Legyen ezek után p_{d} := P r(E_{d}). Akkor p_{1} = P r(E_{1}) = \frac{1}{2^{n}}, valamint P r(E_{d+1}|E_{d}) = 1, és mivel x_{d+1} is egyenletes eloszlású, így P r(E_{d+1}|¬E_{d}) = \frac{1}{2^{n}}. Ebből ha 1 ≤ d < k, úgy

p_{d+1} = p_{d} + (1 − p_{d})\frac{1}{2^{n}} ≤ p_{d} + \frac{1}{2^{n}} ,

ami d-re vonatkozó indukcióval adja, hogy

p_{d} ≤ d\frac{1}{2^{n}} .

Amennyiben E_{k−1} fennáll, úgy f(x_{1}, x_{2}, …, x_{k}) biztosan 1, ellenkező esetben pedig mivel x_{k} is egyenletes eloszlású, ezért f(x_{1}, x_{2}, …, x_{k}) ekkor egyenlő valószínűséggel lehet +1 illetve −1, azaz

E(f) = Δ(f) = p_{k−1} ≤ (k − 1)\frac{1}{2^{n}} ⋄

Ezzel az állítással a 3.23 Következmény segítségével megkaptuk, hogy a mátrix szorzás függvényére a ,,homlokra ragasztott szám” modellben C^{k}(f) = Ω(\frac{n}{2^{k}}).

Raz egyébként azt sejti, hogy ez az alsó becslés egyáltalán nem éles, így a mátrixszorzás függvénye egyike azon függvényeknek, melyekre várható, hogy egy k-ban nem exponenciálisan csökkenő alsó becslést lehet igazolni.

Ramsey típusú becslések

Időnként Ramsey típusú számokkal is lehet becsülni e modellben a kommunikációs komplexitást. A most következő függvényre mindkét irányú becslést e módszerrel adjuk meg.

3.26 DEFINÍCIÓ: Jelölje E_{N}^{k} : {1, …, N}^{k} ⟶ {0, 1} azt a függvényt, amelyre E_{N}^{k}(x_{1}, …, x_{k}) = 1 ⇔ ∑_{i=1}^{k} x_{i} = N. Ez az ún. ,,pontosan N” függvény.

3.27 DEFINÍCIÓ: Definiáljuk a ξ_{k}(N) Ramsey számot a következőképpen:

ξ_{k}(N) az a legkisebb természetes szám, melyre ξ_{k}(N) színnel ki lehet színezni az {1, 2, …, N}^{k−1} halmazt úgy, hogy minden (x_{1}, …, x_{k−1}) és minden λ ≠ 0 mellet ha

(x_{1} + λ, x_{2}, …, x_{k−1})
(x_{1}, x_{2} + λ, …, x_{k−1})

⋮

(x_{1}, x_{2}, …, x_{k−1} + λ)
(x_{1}, x_{2}, …, x_{k−1})

vektorok mind {1, 2, …, N}^{k−1}-ből valók, akkor nem mind egyforma színnel van színezve. Egy ilyen színezést a továbbiakban legálisnak mondunk.

3.28 TÉTEL: C^{k}(E_{N}^{k}) = O(k + log ξ_{k}(N)) .

Bizonyítás: Színezzük ki {1, 2, …, N}^{k−1}-et ξ_{k}(N) színnel legálisan, és tekintsük a következő protokollt E_{N}^{k} kiszámítására:

Minden i ≤ k−1 -re a P_{i} játékos számolja ki az x_{i}^{∗} := N −∑_{j≠i} x_{j} értéket. Megteheti, hisz x_{i} kivételével minden inputot ismer. Az x_{i}^{∗} az az érték, amennyinek az x_{i}-nek kell lennie, hogy az E_{N}^{k} függvény 1-et adjon. Amennyiben ∃i : x_{i}^{∗} ≤ 0, akkor biztos, hogy a szumma nagyobb N-nél, így P_{i} már tudja is, hogy a végeredmény 0. Egyébként az előbbi P_{i}-k számolják ki az (x_{1}, …, x_{i}^{∗}, …, x_{k−1}) színét. A P_{k} játékos számolja az (x_{1}, …, x_{k}) színét. Ezek után a játékosok ellenőrzik, hogy valamennyi szín megegyezik-e. Ha igen, az eredmény 1, ha nem, az eredmény 0. Vegyük észre, hogy ehhez elég az első játékosnak felírnia a számolt színt (log ξ_{k}(N) bit), a többieknek pedig csak egy-egy bitet kell küldeni aszerint, hogy az ő színük megegyezik-e azzal.

Az így számolt eredmény azért helyes, mert amennyiben ∑_{j=1}^{k} x_{j} = N, akkor minden i-re x_{i} = x_{i}^{∗}, így ekkor mindenki az (x_{1}, …, x_{k}) színét számolja, míg ha ∑_{j=1}^{k} x_{j} ≠ N, akkor ∑_{j=1}^{k} x_{j} = N − λ, így ekkor a játékosok által számolt színek az

(x_{1} + λ, x_{2}, …, x_{k−1})
(x_{1}, x_{2} + λ, …, x_{k−1})
⋮
(x_{1}, x_{2}, …, x_{k−1} + λ)
(x_{1}, x_{2}, …, x_{k−1})

vektorok színei. Mivel legális színezést vettük, ezért ezek a színek nem mind egyformák. ⋄

3.29 TÉTEL: C^{k}(E_{N}^{k}) ≥ log ξ_{k}(⌊\frac{N−1}{k−1}⌋) .

Bizonyítás: Tehát azt kell belátnunk, hogy 2^{C^{k}(E_{N}^{k})} ≥ ξ_{k}(⌊\frac{N−1}{k−1}⌋). Tekintsünk egy optimális protokollt E_{N}^{k}-ra, akkor az ehhez tartozó protokoll fa mélysége C^{k}(E_{N}^{k}), ezért leveleinek száma legfeljebb 2^{C^{k}(E_{N}^{k})}. Azonosítsuk a különböző leveleket egy-egy különböző színnel, így azt kell megmutatni, hogy ezekkel a színekkel meg lehet az \{1, …, ⌊\frac{N−1}{k−1}⌋\}^{k−1} elemeit legálisan színezni.

A színezést úgy végezzük, hogy az (x_{1}, …, x_{k−1}) vektor azt a levelet kapja színéül, amelybe az (x_{1}, …, x_{k−1}, N − ∑_{i=1}^{k−1} x_{i}) input mellett a protokoll fa visz. Mivel az x_{i}-k \{1, …, ⌊\frac{N−1}{k−1}⌋\}-ből vannak, így ez értelmes, azaz a k-adik komponens is 1, …, N-be esik. Az így megadott színezés legális, ugyanis ha van k egyszínű vektor az \{1, …, ⌊\frac{N−1}{k−1}⌋\}-ből a következő alakban:

(x_{1} + λ, x_{2}, …, x_{k−1})
(x_{1}, x_{2} + λ, …, x_{k−1})

⋮

(x_{1}, x_{2}, …, x_{k−1} + λ)
(x_{1}, x_{2}, …, x_{k−1})

akkor az alábbi k input azonos levélbe vezet:

(x_{1} + λ, x_{2}, …, x_{k−1}, N − ∑_{i=1}^{k−1} x_{i} − λ)
(x_{1}, x_{2} + λ, …, x_{k−1}, N − ∑_{i=1}^{k−1} x_{i} − λ)
⋮
(x_{1}, x_{2}, …, x_{k−1} + λ, N − ∑_{i=1}^{k−1} x_{i} − λ)
(x_{1}, x_{2}, …, x_{k−1}, N − ∑_{i=1}^{k−1} x_{i})

Ez a 3.5 Tétel miatt azt jelenti, hogy ez a k input egyazon 1-monokromatikus cilinder metszetben van. Mivel a fenti inputok láthatóan egy csillagot alkotnak, így a 3.4 Tétel értelmében a csillag középpontja, (x_{1}, x_{2}, …, x_{k−1}, N − ∑_{i=1}^{k−1} x_{i} − λ) is ebben az 1-monokromatikus cilinder-metszetben van. Ami nyilvánvalóan ellentmondás, hiszen ezen inputra a tagok összege N − λ, így a protokoll 0 eredményt kell adjon. ⋄

3.30 MEGJEGYZÉS: Könnyen belátható, hogy ξ_{k}(N) ≤ k · ξ_{k}(\frac{N}{k}) , ebből az előző tétel úgy fogalmazható, hogy C^{k}(E_{N}^{k}) = Ω(log ξ_{k}(N)). Azaz utóbbi két tételünk a E_{k}^{N} függvény pontos nagyságrendjét adják a ξ_{k}(N) függvényében, viszont sajnos a ξ_{k}(N) értéke nem ismert. Egyedül k = 3 mellett ismert egy jó becslés, ui. tudjuk, hogy ξ_{3}(N) ≤ exp(\sqrt{log N} log log N).

Más alternatíva a protokoll definiálására

E fejezet végén felhívnánk a figyelmet arra, hogy a protokoll fogalmának definiálása sem egyértelmű a többszereplős kommunikáció esetén. A protokollt eddig a kétszereplős modell mintájára úgy definiáltuk a ,,homlokra ragasztott szám” modellben is, hogy olyan függvény, mely kijelöli azt, hogy mikor ki szól, illetve végetérés esetén a végeredményt az elhangzott bitek függvényében. Illetve megmondja, hogy a szólásra következő játékos milyen bitet mondjon a játékos inputja, és az elhangzott bitek függvényében. Azért definiáltuk így a protokoll fogalmát minden esetben, hogy biztosítsuk, hogy a játékosok számára mindig egyértelmű legyen, hogy ki következik szólásra, illetve a protokoll végén minden játékos ugyanarra a végeredményre gondoljon. Viszont egyszerűen úgy is definiálhatjuk a protokoll fogalmát, hogy utóbbi tulajdonságait feltételként szabjuk meg neki. A szakdolgozat szerzőjének tudomása szerint a most következő protokoll definícióval még nem vizsgálta senki a ,,homlokra ragasztott szám” modellt.

3.31 DEFINÍCIÓ: Személyre szóló protokollnak nevezünk egy tetszőleges kommunikációs modellben egy olyan függvénycsoportot, melyben minden szereplőhoz tartozik egy függvény, ami egy adott pillanathoz megmondja, hogy ez a szereplő következik-e szólásra, és ha igen milyen bitet mondjon, illetve ha véget ért a kommunikáció, akkor mi a végeredmény. Mindezt a játékos inputja, és az elhangzott bitek függvényében teszi. E mellet teljesül, hogy:

Minden pillanatban pontosan egy játékos gondolja, hogy ő következik szólásra, kivéve, ha véget ért a kommunikáció (ilyenkor persze egy sem), ekkor pedig minden szereplő ugyanarra a végeredményre gondol.

Látható, hogy a különbség a szólásra következő játékos kijelölésében, és a végeredmény meghatározásában rejlik. Míg a hagyományos protokoll minden játékos számára elérhető adatokból, és ezért minden játékos számára egyértelműen közölte, hogy ki következik szólásra, addig a személyre szóló protokoll esetén a játékosok nem tudják, hogy ki a szólásra következő, csak annyit tudnak, hogy éppen ők jönnek, vagy sem. E mellet feltételként szabtuk meg, hogy egyértelmű legyen, ki küldjön éppen bitet. Ezen túl személyre szóló protokollnál azt is megengedjük, hogy a játékos által gondolt végeredmény is függjön a játékos inputjától, szintén feltételként megszabva, hogy ez minden játékosnál ugyanaz legyen. Könnyen látszik, hogy:

3.32 ÁLLÍTÁS: A Yao-féle kétszereplős kommunkációs modellben a hagyományos és a személyre szóló protokoll fogalma megegyezik.

Bizonyítás: Egy hagyományos protokoll olyan függvényekből áll, melyek az A és B játékosok közötti kommunikáció függvényében határozzák meg a következő játékost, illetve végetérés esetén a végeredményt. Az elküldendő bit meghatározása megegyezik a két esetben. Így egy hagyományos protokoll megfelel egy személyre szóló protokollnak, az ugyanis még ennél több dolog függvényében határozza meg az előbbieket. Pontosabban a szólásra következő játékost, és végeredményt kijelölő függvényből mindkét játékosnak adva egy-egy példányt egy személyre szóló protokollt kapunk. Azt kell még megmutatni, hogy a kétszereplős modellben a személyre szóló protokollnál a játékos szólásra következése, és a végeredmény ténylegesen nem függhet a játékos inputjától. Ez pedig azért igaz, mert különben létezne olyan x, x^{∗} ∈ X, y ∈ Y, és s bitsorozat, hogy az s elhangzása után, ha B-nél y input van, és A-nál x, akkor A azt hiszi, hogy ő jön szólásra, viszont ha A-nál x^{∗} van, akkor azt hiszi, hogy B következik. Ez biztosan nem lehet, ugyanis B is gondol valamelyikükre, így az egyik esetben egyszerre próbálnának beszélni.⋄

Sőt a k szereplős táblás kommunikációs modellben is egybeesik a két fogalom, ha az inputok között nincs átfedés (mindenki csak egy inputot lát), a fenti bizonyítás ekkor is működik.

Viszont a ,,homlokra ragasztott szám” modellben a hagyományos, és személyre szóló protokollok eltérnek. Látható például, hogy egy személyre szóló protokoll megengedi azt, hogy a P_{2}, P_{3}, …, P_{k} játékosok közül a mindannyiuk számára elérhető x_{1} input alapján dőljön el, hogy ki következik szólásra.

Ez azt eredményezi, hogy a kommunikációs komplexitása is különböző lehet egy függvénynek a két protokollfogalom mellett. Nézzünk meg erre egy egyszerű példát:

Legyen k = 3, és f az a függvény, amelyre f(x_{1}, x_{2}, x_{3}) érték az x_{2} első bitjével egyezik meg ha x_{1} első bitje 0, és x_{3} első bitjével egyezik meg, ha x_{1} első bitje 1.

3.33 ÁLLÍTÁS: Erre az f-re C_{S}^{3}(f) < C^{3}(f), ahol az S az indexben a személyre szóló protokollokra utal.

Bizonyítás: Személyre szóló protokollt tudunk adni 1 bit kommunikációval, hiszen azt mondjuk, hogy x_{2} következzék szólásra, ha x_{1} első bitje 1, és x_{3} következik szólásra, ha x_{1} első bitje 0. Ekkor a szólásra következő játékos látja a végeredményt, és így fel tudja írni a táblára. Viszont hagyományos protokoll legalább 2 bit kommunikációt igényel, ugyanis egy 1 bites kommunikációban a bitet felíró játékost mindentől függetlenül kell kijelölni, és bárkit is jelölünk ki, könnyen adható olyan input, melyre az a játékos nem tudja az eredményt felírni.⋄

Az a kérdés, hogy a két kommunikációs komplexitás között mekkora eltérés lehet. Mint láttuk a személyre szóló definíció általánosabb a hagyományosnál, így C_{S}^{k}(f) ≤ C^{k}(f) mindig teljesül, de mennyivel lehet C_{S}^{k}(f) kisebb. Erre egy felső korlátot tudunk adni.

3.34 TÉTEL: (k + 1)C_{S}^{k}(f) + 1 ≥ C^{k}(f) minden f-re.

Bizonyítás: Egy személyre szóló protokollból mindig tudunk készíteni egy hagyományosat a következőképpen. Amikor a személyre szóló protokoll szerint egy játékos felír egy bitet a táblára, akkor még ez előtt minden játékos írjon fel egy-egy bitet indexük szerinti sorrendben, méghozzá 1-est pontosan az a játékos írjon, aki szólásra következik. Ezzel a módosítással már egy hagyományos protokollhoz jutottunk, hiszen a táblán lévő bitekből mindig megmondható, hogy ki következik szólásra. Esetleg szükség lehet még egy bitre, az eredmény felírására, hisz elképzelhető, hogy ez nem történt meg, és a játékosok még inputjuktól is függően gondolnak valamilyen végeredményre. Ebből következik a tétel.⋄

Sejthető esetleg, hogy ez már majdnem éles, és adható olyan f függvény, amelyre körülbelül egy (k − 1) szorzóval nagyobb a hagyományos értelemben vett kommunikációs komplexitás. Ennek bizonyításához azonban mindenképpen valami új technikára lenne szükség. Ugyanis könnyen látszik, hogy a protokoll fa adott levelébe érkező inputok halmaza az altarnatív protokoll definíció mellett is cilinder metszetet alkot. Ezáltal az alsó becslési technikák mind működnek ekkor is, így ha eltérést szeretnénk bizonyítani, úgy a hagyományos komplexitásra más módszerrel kell adnunk egy jobb alsó becslést.

4. A csillag modell

A csillag modellben, melyet e szakdolgozatban elsőként vizsgálunk k játékos, P_{1}, P_{2}, …, P_{k} vesz részt, egy-egy inputtal a {0, 1}^{n}-ből. Mindegyikük kapcsolatban áll egy k +1-edik, központi P_{0} játékossal, aki azonban nem rendelkezik inputrésszel. Így kell a szereplőknek egy f : ({0, 1}^{n})^{k} ⟶ {0, 1} függvény értékét kiszámolják minimális kommunikáció felhasználásával, ahol a kommunikáció a k kapcsolaton elhangzott kommunikációk összege. Tehát az 1. fejzetben ismertetett kategorizálással ez a modell személyes kommunikáción alapuló modell, ahol a kommunikációs gráf egy k ágú csillag, és inputrésszel a központi játékoson kívül mindenki rendelkezik.

3.abra

Ez a modell a 2. fejezetben tárgyalt lineáris hálózatra annyiban hasonlít, hogy az inputtal rendelkező játékosok input nélküli közbülső szereplőkön keresztül kénytelenek kommunikálni. A 3. fejezetbeli modellel pedig az a közös vonás, hogy sok szereplő rendelkezik inputtal.

Nézzük meg, hogyan kell e modellben a megengedett protokollt definiálni ahhoz, hogy akár a 2. fejezetben egy olyan aszinkron modellt kapjunk, melyben egy protokoll mindig lefuttatható, és minden lefutása ugyanazon bitsorozatokat eredményezi valamennyi kapcsolaton: Minden kapcsolathoz rendeljünk itt is egy protokoll fát, mely azon a kapcsolaton addig elhangzott bitek függvényében meghatározza, hogy a két játékos közül melyik következik szólásra, illetve ha már egyikük sem, akkor számukra mi a végeredmény. Ha egy kapcsolaton az inputtal rendelkező játékos következik szólásra, akkor a protokoll megadja, hogy a játékos az inputja, és a kapcsolaton addig elhangzott bitek függvényében milyen bitet küldjön a központnak. Az aszinkronitás miatt ezt a bitet bármikor elküldheti, de a szándékos blokkolás kiküszöbölése érdekében véges időn belül ezt meg is kell tennie. A protokollhoz tartozik még k függvény, Φ_{1}, Φ_{2}, …, Φ_{k} , ahol Φ_{i} függvény azt adja meg, hogy ha az i-edik kapcsolaton a P_{0} következik szólásra, akkor az összes kapcsolaton addig elhangzott bitek függvényében a központ milyen bitet küldjön a P_{i}-nek. A Φ_{i} értékkészlete {0, 1, ⊥} , és ⊥ az érték pontosan akkor, ha az i-edik kapcsolaton nem a központ következik szólásra, vagy a központ még biteket vár más játékosoktól ahhoz, hogy eldöntse, milyen bitet küldjön P_{i}-nek. A szükséges feltételek hasonlóak a lineáris hálózatra tettekkel:

(1) Konzisztencia a protokoll fákkal: Ha az i-edik kapcsolaton adott pillanatban P_{i} következik szólásra, akkor e pillanatban a Φ_{i} értéke ⊥ (azaz a központ nem szólhat).

(2) Nincs szándékos blokkolás: Ha egyik kapcsolaton sem az inputtal rendelkező játékos következik szólásra (azaz minden kapcsolaton vagy P_{0} jön, vagy már nincs további kommunikáció), és a protokoll még nem fejeződött be, akkor létezik olyan i, hogy a Φ_{i} értéke nem ⊥.

(3) A központ nem gondolhatja meg magát: Ha Φ_{i} értéke nem ⊥, akkor ez az érték már nem változhat meg további kommunikáció hatására.

(4) Egyhangúság: Ha a protokoll befejeződött, akkor a k kapcsolathoz tartozó protokoll fák azonos eredményt jelentő levélben kötöttek ki. Ez a végeredmény.

A lineáris hálózatnál azt vizsgáltuk meg, hogy az ottani kommunikációs komplexitás hogyan viszonyul a hagyományos kétszereplős modellbelihez. Itt a csillag modellben viszont a szereplők egy k-változós függvényt számítanak ki, ezért kapcsolatot csak olyan modellbeli kommunikációs komplexitással kereshetünk, ahol ugyanez áll fenn. A modell, amelyhez viszonyítunk az a modell lesz, amelyben k szereplő - mindegyike saját inputtal a {0, 1}^{n}-ből - szeretné kiszámítani egy f : ({0, 1}^{n})^{k} ⟶ {0, 1} k-változós függvény értékét táblás kommunikácikóval (ld. 1. fejezet). Ezt a modellt a továbbiakban táblás modellnek hívjuk majd.

Jelölje a továbbiakban egy k-változós f függvény kommunikációs komlexitását a táblás modellben C_{k}^{T} (f), a csillag modellben pedig C_{k}^{∗}(f). Mind alsó, mind felső becslést fogunk adni a C_{k}^{∗}(f)-re a C_{k}(f) függvényében.

4.1 TÉTEL: C_{k}^{∗}(f) ≤ k · C_{k}^{T} (f)

Bizonyítás: Tekintsünk egy optimális, azaz C_{k}^{T} (f) bitet használó protokollt az f kiszámítására a táblás modellben. Amikor az i-edik játékos e protokoll szerint felír a táblára egy bitet, akkor a csillag modellben a P_{i} játékos küldje el a bitet a központnak, aki pedig továbbítsa az összes többi k − 1 játékosnak. Így a csillag modellben szimuláljuk a táblás kommunikációt, hiszen valóban minden bitről minden játékos tudomást szerez. A táblás modellbeli minden bithez k darab bit elküldése szükséges e szimulációhoz, tehát a tételbeli felső becslés valóban fennáll.⋄

4.2 TÉTEL: Ha f nem konstans, akkor C_{k}^{∗}(f) ≥ C_{k}^{T} (f) + (k − 1).

Bizonyítás: Tekintsünk egy optimális, azaz C_{k}^{∗}(f) bitet használó protokollt az f kiszámítására a csillag modellben. Adunk egy protokollt a táblás modellre, mely legfeljebb C_{k}^{∗}(f) kommunikációt használ. Amikor az i-edik játékos (i ≠ 0) egy bitet küld a központnak a csillag modellben, akkor a táblás modellben az i-edik játékos írja fel ezt a bitet a táblára. Amennyiben egyszerre több inputtal rendelkező játékos is szólásra következik, akkor köztük valamilyen előre meghatározott sorrend (például indexük) döntse el, hogy kit szimulálunk először. Ezek után amikor a központ küld egy bitet például a jedik játékosnak a csillag modellben, akkor a táblás modellben ne történjék semmi. Nem is kell, hiszen a központ az elküldött bitet a hozzá addig beérkezett bitekből számolta ki, ezek viszont mind a táblán vannak, így a j-edik játékos ezt maga is kiszámolhatja. Így a táblás modellre adott protokoll annyival kevesebb bitet használ a csillag modellbelinél, ahány bit a központból továbbítódott valamely inputtal rendelkező játékos felé. Ebből persze C_{k}^{∗}(f) ≥ C_{k}^{T} (f) azonnal következik, méghozzá az f-re tett feltétel nélkül is. Azt hogy a tétel is igaz azt a következőkben igazoljuk.

Ha f nem konstans, akkor a csillag modellben minden kapcsolaton el kell legalább egy bitnek hangzania valamilyen irányban, hiszen ha mondjuk az i-edik kapcsolaton nincs kommunikáció, ez azt jelentené, hogy P_{i} számára a végeredmény semmitől sem függ, tehát f konstans. Ha a csillag modellbeli kommunikáció során minden inputtal rendelkező játékoshoz érkezik bit a központból, akkor legalább k bitet megspórolunk a táblás modellben a fenti szimulációval. Akkor van csak gond, ha valamely inputtal rendelkező játékos, mondjuk P_{i} nem kap bitet a központból. Ez azt jelenti, hogy ő az inputjából már biztosan tudja a végeredményt, azaz nála egy a függvény értékét rögzítő input van. Ha egyetlen játékosnál van csak rögzítő input, akkor (k−1) bitet még mindig megspórolunk. Tegyük fel, hogy több játékosnál is lehet rögzítő input. Vegyük észre, hogy ekkor ezek csak ugyanazt a függvényértéket rögzíthetik, küln̈ben ellentmondás lenne, ha az egyik játékos egy nullát, másik pedig egy 1-et rögzítő inputot kapna. Legyen P_{i} a legkisebb indexű játékos, aki rögzítő inputot kapott.

Az i-edik kapcsolaton ez esetben is kell kommunikációnak történnie, amely tehát kizárólag P_{i}-től a központ felé irányul. Tehát valamilyen bitsorozattal P_{i} tájékoztatja a központot, hogy ő már tudja a végeredményt. Módosítsuk ekkor a fenti táblás szimulációnkat úgy, hogy amennyiben P_{i} ezt a jelsorozatot írja fel a táblára, akkor a játékosok azonnal tudják a végeredményt, ezáltal nincs is szükség további kommunikációra. Igazából a játékosok csak azt tudják meg, hogy P_{i}-nél rögzítő input van, de mint láttuk ez csak egyféle függvényértéket rögzíthet, így a végeredményt is tudják. Ekkor az i-nél nagyobb sorszámú kapcsolatokon még nem hangzott el bit, és mivel láttuk, hogy legalább egy bit el fog hangzani, így ezeket mind megspóroltuk. Az i-nél kisebb sorszámú kapcsolatokon pedig szintén megspóroltunk legalább egy-egy bitet, hisz azokon küldött, vagy küldeni fog a központ kifelé bitet. Összefoglalva tehát bárhogy is zajlik a csillag modellben a kommunikáció, a táblás modelllben (k − 1) bitet megspórolva szimulálhatjuk azt, ebből pedig adódik a tétel.⋄

A továbbiakban azt vizsgáljuk, hogy a 4.1 és 4.2 Tételek által adott becslések mennyire élesek. A most következő tétel azt mondja, hogy a 4.1 Tétel becslése éles.

4.3 TÉTEL: Létezik olyan f függvény, melyre C_{k}^{∗}(f) ≥ k · C_{k}^{T} (f) − k^{2}.

Bizonyítás: Legyen az f a k-változós egyenlőség függvény, vagyis az az f : ({0, 1}^{n})^{k} ⟶ {0, 1} függvény, melyre f(x_{1}, x_{2}, …, x_{k}) = 1 pontosan akkor, ha x_{1} = x_{2} = ⋯ = x_{k} áll fenn. Akkor C_{k}^{T} (f) ≤ n + (k − 1), hiszen elég ha P_{1} felírja a táblára a teljes inputját, majd ezek után a többi (k − 1) játékos egy-egy bitet küld, amely 1-es ha az ő inputja megegyezik a felírttal, és 0, ha nem. Ekkor az f értéke pontosan akkor 1, ha a (k − 1) utoljára felírt bit mind 1-es.

Megmutatjuk, hogy az egyenlőség függvényre a csillag modellben C_{k}^{∗}(f) ≥ kn. Ebből C_{k}^{∗}(f) ≥ kn ≥ k(C_{k}^{T} (f)−(k−1)) = k·C_{k}^{T} (f)−k(k−1), ami igazolja a tételt. Vegyünk ennek érdekében egy jó protokollt a csillag modellben az egyenlőség függvény kiszámítására. Legyen x, y ∈ {0, 1}^{n}, ekkor azt állítjuk, hogy az (x, x, …, x) és az (y, y, …, y) input kas mellett egy adott (tetszőleges) kapcsolaton más bitsorozatok hangzanak el. Ugyanis ha például az i-edik kapcsolaton ugyanaz a kommunikáció hangzana el az (x, x, …, x) és az (y, y, …, y) input k-asok mellett, akkor ugyanez a bitsorozat hangzana el az i-edik kapcsolaton akkor is ha P_{i} játékos y-t, az összes többi pedig x-et kapna inputjául. Hiszen a {P_{j} : j ≠ i} játékoscsoport nem tudja, hogy P_{i}-nél milyen input van, így köztük ugyanaz történik ha P_{i}-nél az x illetve az y van, amennyiben persze ő is ugyanazokat a biteket küldi. Ugyanígy P_{i} sem tudja, hogy a többi inputtal rendelkező játékosnál csupa x, vagy csupa y input van. Viszont ez ellentmondás, hiszen ha az i-edik kapcsolaton a kommunikáció ugyanaz ha P_{i}-nél y van, a többieknél pedig x, illetve ha mindenkinél x van, akkor P_{i} a kommunikáció végén ugyanarra a végeredményre is gondol, viszont az eredmény az első esetben 0, az utóbbiban pedig 1. Ebből persze az is következik, hogy minden kapcsolat esetén a rajta elhangzó bitsorozatok halmaza prefix-mentes halmazt alkot, midőn az input végigfut az {(x, x, …, x) : x ∈ {0, 1}^{n}} halmazon. Jelölje s_{l}(x) az l-edik kapcsolaton elhangzott bitsorozatot az (x, x, …, x) input mellett. Akkor alkalmazva a prefix-mentes halmazokra vonatkozó 2.4 Lemmát azt kapjuk, hogy

∑_{x∈{0,1}^{n}} ∑_{l=1}^{k} |s_{l}(x)| = ∑_{l=1}^{k} ∑_{x∈{0,1}^{n}} |s_{l}(x)| ≥ k · 2^{n} log 2^{n} = 2^{n} · kn

Ebből viszont következik, hogy létezik olyan x ∈ {0, 1}^{n}, hogy az (x, x, …, x) input mellet az összes kommunikáció legalább kn.⋄

A 4.2 Tételben szereplő (k − 1)-es különbség a két kommunikációs komplexitás között biztosan nem javítható k-nál nagyobbra, ugyanis ha az egyenlőségtesztet nézzük az inputok első bitjeire, akkor ennek a függvénynek a kommunikációs komplexitása könnyen igazolható, hogy a táblás modellben k (mindenki felírja az első bitet a táblára), a csillag modellben pedig 2k (mindenki beküldi az első bitjét a központba, az pedig mindenkit értesít az eredményről). Ilyen értelemben tehát éles a 4.2 Tétel becslése. Igazából viszont az az érdekes kérdés, hogy teljesül-e valamilyen k-tól függő c ≥ 1-re, hogy C_{k}^{∗}(f) ≥ c · C_{k}^{T} (f) + F (k) , ahol F (k) valamilyen k-tól függő hibatag. Ezt nem tudjuk, így a 4.2 Tétel nem tekinthető élesnek, viszont tudjuk, hogy a c-t az (1 + \frac{1}{k−1}) érték alatt érdemes csak keresni, hiszen:

4.4 TÉTEL: Majdnem minden f : ({0, 1}^{n})^{k} ⟶ {0, 1} függvényre (n → ∞ esetén) C_{k}^{∗}(f) ≤ (1 + \frac{1}{k−1}) · C_{k}^{T} (f) + k.

Bizonyítás: Azt tudjuk, hogy C_{k}^{∗}(f) ≤ kn + k , hiszen a csillag modellben minden függvényre alkalmazható a triviális protokoll, mely során valamennyi szereplő beküldi az inputját a központba (kn bit), majd a központ az f értékének kiszámítása után az eredményről minden játékost tájékoztat (további k bit). Elég ha megmutatjuk, hogy C_{k}^{T} (f) ≥ (k − 1)n teljesül majdnem minden f függvényre, ugyanis ebből

C_{k}^{∗}(f) ≤ kn + k = \frac{k}{k − 1}(k − 1)n + k ≤ \frac{k}{k − 1}C_{k}^{T} (f) + k

ami a bizonyítandó állítás.

A bizonyítás leszámlálással történik.

Az f : ({0, 1}^{n})^{k} ⟶ {0, 1} függvények száma f_{n,k} = 2^{2^{nk}}, hiszen ({0, 1}^{n})^{k}-nak 2^{nk} eleme van, és egy függvény e halmaz minden eleméhez kétféle értéket rendelhet.

A táblás modellben a legfeljebb t bitet használó protokollok száma (amit p_{t} jelöl) becsülhető felülről a (2k)^{2^{t}} · 2^{2^{n}·2^{t}} értékkel, hiszen egy protokoll a táblás modellben két függvényből áll. Az egyik az addig táblára került bitek függvényében megadja, hogy ki következik szólásra, amennyiben persze még nem ért véget a protokoll. Mivel ekkor a táblán lévő bitek száma legfeljebb (t − 1), így ezt legfeljebb k^{∑_{i=0}^{t−1} 2^{i}}-féleképpen teheti meg. Ha pedig már véget ért (ekkor legfeljebb t bit van a táblán), akkor a protokoll meghatározza a tábla függvényében a végeredményt, erre tehát legfeljebb 2^{2^{t}} lehetőség van. Kihasználva, hogy ∑_{i=0}^{t−1} 2^{i} ≤ 2^{t} azt kapjuk, hogy az eddigiek meghatározására legfeljeb (2k)^{2^{t}} lehetőség van. A protokoll másik függvénye az ily módon kijelölt játékos inputjának, és a tábla addigi tartalmának függvényében adja meg, hogy a kijelölt játékos milyen bitet írjon a táblára. Ennek viszont legfeljebb 2^{2^{n}·2^{t}} módja lehet. Vagyis azt kaptuk, hogy p_{t} ≤ (2k)^{2^{t}} · 2^{2^{n}·2^{t}} = 2^{2^{t}(2^{n}+log k+1)}.

Amennyiben t = (k − 1)n − 1, és log k + 1 ≤ 2^{n−1} (ez utóbbi feltehető, hisz n → ∞ esetet nézzük), akkor

2^{t}(2^{n} + log k + 1) ≤ \frac{3}{4} · 2^{nk}.

Ebből

\frac{p_{t}}{f_{n,k}} ≤ \frac{2^{2^{t}(2^{n}+log k+1)}}{2^{2^{nk}}} ≤ 2^{− \frac{1}{4} 2^{nk}}

ami nullához tart n → ∞ esetén. Viszont p_{t} a legfeljebb t bitet használó protokollok száma, tehát felülről becsli a legfeljebb t kommunikációs komplexitású függvények számát, így ezen függvények aránya az összes függvények között 0-hoz tart. Ez pedig azt jelenti, hogy majdnem minden függvény kommunikációs komplexitása a táblás modellben legalább (k − 1)n.⋄

Mivel ez a legjobb alsó határ, amit C_{k}^{∗}(f)-fel el tudtunk érni, így sejthetnénk azt is, hogy minden f-re C_{k}^{∗}(f) ≥ (1 + \frac{1}{k−1})C_{k}^{T} (f) teljesül. Azonban ez biztosan nem igaz. Erre éppen a 2. fejezetben láthattunk egy ellenpéldát. Vegyük ugyanis észre, hogy k = 2 mellett a Tiwari féle lineáris hálózat modell megegyezik a csillag modellel.A sejtés k = 2 mellett, azt állítaná, hogy C_{2}^{∗}(f) ≥ 2 · C_{2}^{T} (f) , ami éppen Tiawri sejtése a 2 hosszú lineáris hálózatra, amiről megmutattuk, hogy nem igaz. Tiwari sejtésére az ellenpélda egy olyan f függvény volt, melyre ottani jelöléssel élve C_{k}(f) ≤ (\frac{3}{4} + o(1)) · k · C(f) teljesült. Viszont k = 2 mellett az ottani C_{2}(f), mint említettük azonos az e fejezetben definiált C_{2}^{∗}(f)-fel, és az ottani C(f), azaz a hagyományos kétszereplős kommunikációs komplexitás pedig természetesen megegyezik a kétszereplős táblás modellbeli komplexitással, amit pedig e fejezetben C_{2}^{T} (f)-fel jelölünk. Áttérve tehát az e fejezetben használt jelölésekre olyan f-et ismerünk a 2. fejezetből, amelyre C_{2}^{∗}(f) ≤ (\frac{3}{4} + o(1)) · 2 · C_{2}^{T} (f) = (\frac{3}{2} + o(1)) · C_{2}^{T} (f).

Ha azonban a protokolokra mind a táblás, mind a csillag modellben egy igen erős megkötést teszünk, akkor ez az eddig rossz sejtés igazzá, és ezáltal a 4.4 Tétel élessé válik. Ez az erős megkötés pedig a ,,nemtörődöm” tulajdonság.

Azt mondjuk egy protokollra, hogy nemtörődöm protokoll, ha az, hogy mikor ki szóljon a játékosok közül az nem függ az addig elhangzott bitektől, és ezáltal az inputoktól sem. A protokoll tehát előre megmondja, hogy mikor, ki, kinek küld egy bitet.

4.5 TÉTEL: Ha a táblás modellben, és a csillag modellben egyaránt csak nemtörődöm protokollokat engedünk meg, és az új komplexitásokat kalappal különböztetjük meg az eddigiektől, akkor minden f függvényre teljesül, hogy Ĉ_{k}^{∗}(f) ≥ (1 + \frac{1}{k−1}) · Ĉ_{k}^{T} (f)

Bizonyítás: Tekintsünk egy optimális, azaz Ĉ_{k}^{∗}(f) bitet használó nemtörődöm protokollt az f kiszámítására a csillag modellben. Konstruálunk egy nemtörődöm protokollt a táblás modellre, amely legfeljebb (1− \frac{1}{k})·Ĉ_{k}^{∗}(f) bitet használ, ebből Ĉ_{k}^{T} (f) ≤ (1− \frac{1}{k})·Ĉ_{k}^{∗}(f), amiből a tétel átrendezéssel következik.

Legyen P_{l} az a játékos, aki az adott nemtörődöm protokoll esetén a legkevesebb bitet kommunikálja a központtal. Ez tehát ebben az esetben nem függ az inputoktól. Tekintsük a táblás modellben a következő protokollt:

Amikor a csillag modellben P_{i} játékos beküld egy bitet a központba (i ≠ l), akkor a táblás modellben a P_{i} játékos felírja ezt a bitet a táblára, ha viszont a csillag modellben P_{l} küld bitet a központnak, akkor a táblás modellben nem történik semmi. Szintén nem történik semmi, ha a központ küld bitet P_{l}-nek. Végezetül ha a központ küld a csillag modellben egy bitet a P_{i} (i ≠ l) játékosnak, akkor ezt a bitet a táblás modellben a P_{l} játékos fogja felírni a táblára. Ezt azért tudja megtenni, mert a központ az alapján dönti el, hogy milyen bitet küld a P_{i}-nek, hogy milyen biteket kapott eddig a játékosoktól. Amiket a P_{j} (j ≠ l) játékosoktól kapott, azok fenn vannak a táblán, így P_{l} birtokában van az összes kommunikációnak, hogy szimulálja a központ tevékenységet.

A táblás modellre így egy olyan protokollt adtunk, amelyben a csillag modellhez képest megspóroltuk azt a kommunikációt, amely a központ és P_{l} között zajlott. Ez legalább \frac{1}{k} Ĉ_{k}^{∗}(f) bit megtakarítást jelent, hiszen a P_{l} a legtöbbet, és így legalább a kommunikáció k-ad részét kommunikálta a központtal.

4.6 MEGJEGYZÉS: Ha nem tesszük fel a nemtörődöm tulajdonságot a megengedett protokollokról, hanem a szokványos módon értelmezzük azokat (tehát az, hogy mikor ki következik, az az addig elhangzott bitektöl is függ), akkor ezzel a módszerrel is csak annyit tudunk bizonyítani, hogy C_{k}^{∗}(f) ≥ C_{k}^{T} (f). Hiszen azt, hogy melyik kapcsolaton fogjuk megspórolni a kommunikációt az inputoktól függetlenül kellett megadnunk, és előfordulhat olyan input, melyre ezen a kapcsolaton csak minimális az elhangzó kommunikáció.

4.7 MEGJEGYZÉS: Ha csak a nemtörődöm protokollokkal foglalkozunk, attól még a 4.4 Tétel igaz marad, ugyanis a csillag modellben a triviális protokoll is egy nemtörődöm protokoll, és a leszámlálás is ugyanúgy működik, mint a hagyományos protokoll értelmezéssel. Azzal a különbséggel, hogy annak kijelölésére, hogy mikor ki beszél nem csak hogy legfeljebb k^{2^{t}} lehetőség van, hanem ennél kevesebb: k^{t}, de ettől még a k^{2^{t}} felső becslés csak még inkább igaz. Ebből az látszik, hogy a nemtörődöm protokollokra a Ĉ_{k}^{∗}(f) ≥ (1 + \frac{1}{k−1}) · Ĉ_{k}^{T} (f) egy éles alsó becslés.

Azonban a nemtörődöm tulajdonság egy igen erős megkötés a protokollokra, amit például az is mutat, hogy Tiwari sejtése nemtörődöm protokollokra szorítkozva azonnal igazzá válna. Rádásul rendkívül egyszerűen igazolható is: Tekintsük a lineáris hálózat kétszereplős szimulációját bármely kapcsolat mentén. Akkor léteznek olyan x, y inputok, melyek mellett ezen a kapcsolaton Ĉ(f) bit hangzik el. Mivel egy nemtörődöm protokoll az inputoktól függetlenül adja meg, hogy mikor ki beszél, így minden kapcsolatra kénytelen Ĉ(f) bit kommunikációt kijelölni. Ebből azonnal következik a Ĉ_{k}(f) ≥ k · Ĉ(f) állítás.

Összefoglalva tehát eddigi eredményeinket arra jutottunk, hogy nemtörődöm protokollok esetén (1 + \frac{1}{k−1}) · Ĉ_{k}^{T} (f) ≤ Ĉ_{k}^{∗}(f) ≤ k · Ĉ_{k}^{T} (f) , ahol ráadásul a becslés mindkét oldalról éles. A hagyományos módon értelmezett protokollok esetén viszont azt tudjuk, hogy C_{k}^{T} (f) + (k − 1) ≤ C_{k}^{∗}(f) ≤ k · C_{k}^{T} (f) , és az alsó irányból nem tudjuk, hogy éles-e a becslés.

Felhasznált 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