Kommunikációs komplexitás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. december 30-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Az elméleti számítástechnikában a kommunikációs komplexitás azt vizsgálja, hogy mennyi kommunikáció szükséges egy olyan probléma megoldásához, amelynek paraméterei megoszlanak két vagy több fél között. Ezt a fogalmat Andrew Yao vezette be 1979-ben [1] , aki a következő problémát vizsgálta két résztvevőnél, akiket hagyományosan Alice és Bobnak hívnak . Alice egy n bites x karakterláncot, Bob pedig egy n bites y karakterláncot kap , és az a céljuk , hogy az egyikük (például Bob) egy definiált és mindkét fél által ismert függvényt számoljon ki a legkevesebb kommunikáció mellett . . Természetesen mindig így is számolhatnak : Alice elküldi a teljes n-bites karakterláncát Bobnak, aki ezután kiértékeli a függvényt . Ezért a feladat e megfogalmazásánál érdekes, hogy mely f függvényekre van mód n bitnél kevesebb átvitellel számítani. Fontos megjegyezni, hogy ebben a feladatban nem érdekel minket az Alice vagy Bob által végzett számítások bonyolultsága , vagy az ezekhez a számításokhoz használt memória mérete. $f(x,y)$ $f(x,y)$ $f(x,y)$ $f(x,y)$

Ez az elvont két résztvevős probléma (amelyet két résztvevős kommunikációs komplexitásnak neveznek) és általános formája sok résztvevővel a számítástechnika különböző területein merül fel: például a nagyméretű integrált áramkörök tervezésénél a felhasznált energia minimalizálásának szükségessége a a különböző komponensek közötti elektromos jelek száma az elosztott számítás során. A kommunikációs komplexitást az adatstruktúrák és algoritmusok tanulmányozásában, a számítógépes hálózatok optimalizálásában, a számítási komplexitás és a bizonyítási komplexitás elméletében és más területeken is alkalmazzák.

Formális definíció

Legyen kezdetben adott valamilyen függvény , ahol a legtipikusabb utasításban . Alice kap , Bob kap . Alice és Bob egy bitenkénti üzenetváltással (valamilyen előre meghatározott kommunikációs protokoll használatával ) úgy akarják kiszámítani az értéket , hogy a kommunikáció végén legalább egyikük tudja az értéket . $f:X\time Y\to Z$ $X=Y=\{0,1\}^{n},Z=\{0,1\}$ $x\X-ben$ $y\-ban Y$ $z=f(x,y)$ $z$

A függvény kiszámításának kommunikációs bonyolultságát $f$ , amelyet jelöl , a kommunikációs bitek minimális számaként határozzuk meg, amely a legrosszabb esetben is elegendő a probléma megoldásához (vagyis ez a bitszám elegendő bármely párhoz ). $D(f)$ $x,y$

E definíció alapján célszerű az f függvényt az A mátrix által adott függvénynek tekinteni , amelyben a sorok elemekkel , az oszlopok pedig elemekkel vannak indexelve . Ennek a mátrixnak az x és y elemekkel indexelt celláiba a megfelelő f értéke van írva , azaz . Alice és Bob ismeri az f függvényt , ezért ismeri az A mátrixot . Ezután Alice az x sorszámot , Bob pedig az y oszlopszámot kapja , és a feladatuk az, hogy meghatározzák a megfelelő cellába írt értéket. Ezért, ha valamelyik játékos egyszerre ismeri az oszlop- és a sorszámot, akkor a megfelelő cellában lévő értéket is tudni fogja. A kommunikáció kezdetén minden játékos semmit nem tud a másik játékos számáról, így Alice szemszögéből a válasz tetszőleges érték lehet az x sorban, Bob szemszögéből pedig az y oszlop bármely értéke. . Az egyes átvitt bitekkel való kommunikáció során új információk jelennek meg, amelyek lehetővé teszik a játékosok számára, hogy levágjanak néhány lehetséges cellát. Például, ha egy ponton Alice elküldi a b bitet , akkor Bob szemszögéből Alice összes lehetséges bemenete két halmazra oszlik: amelyekre Alice küldene , és amelyekre Alice küldene . A b bit értékének ismeretében Bob levágja Alice néhány lehetséges bemenetét, és így leszűkíti a lehetséges cellák körét az ő szemszögéből. Ebben az esetben a külső szemlélő szemszögéből minden üzenet után vagy a lehetséges sorok halmaza, vagy a lehetséges oszlopok halmaza leszűkül, és így a lehetséges cellák halmazát az A mátrix valamely részmátrixa szűkíti . $x\X-ben$ $y\-ban Y$ $A_{\mathrm {x,y} }=f(x,y)$ $b=0$ $b=1$

Formálisabban egy halmazt (kombinatorikus) téglalapnak nevezünk , ha abból következik , hogy és . Ekkor az A mátrix minden részmátrixa hozzá van rendelve egy R kombinatorikus téglalaphoz úgy, hogy , ahol és . Tekintsük most azt a helyzetet, amikor k bitet már átvittek a résztvevők között. Adja meg ezt az első k bitet a karakterlánc . Ekkor lehetséges olyan bemenetpárok halmazát definiálni , amelyeken az első k egyenlő $R\subseteq X\times Y$ $(x_{1},y_{1})\in R$ $(x_{2},y_{2})\in R$ $(x_{1},y_{2})\in R$ $(x_{2},y_{1})\in R$ $R=M\times N$ $M\subseteq X$ $N\subseteq Y$ ${\displaystyle h\in \{0,1\}^{k))$ $T_{\mathrm {h} }\subseteq X\times Y$ $h$

T_{\mathrm {h} }=\{(x,y):k

- kommunikációs bit a bemeneteken egyenlő

{\megjelenítési stílus (x,y)}

{\displaystyle h\))

Ekkor egy kombinatorikus téglalap, azaz az A mátrix egy részmátrixát határozza meg . ${\displaystyle T_{\mathrm {h} ))$

Példa: EQ függvény

Hadd . Tekintsünk egy olyan problémát, amelyben Alice és Bob meg akarja állapítani, hogy ugyanazokat a karakterláncokat kapják-e, vagyis ellenőrizni akarják, hogy . Könnyen kimutatható, hogy ennek az egyenlőségi tesztnek (EQ) a megoldásához a legrosszabb esetben n bitet kell továbbítanunk , ha erre a kérdésre pontosan meg akarunk válaszolni minden lehetséges x és y párra . $X=Y=\{0,1\}^{n},Z=\{0,1\}$ $x=y$

Ebben az esetben az x és y karakterlánc három bitből áll. Az egyenlőségi függvényt ebben az esetben a következő mátrix határozza meg, ahol a sorokat Alice bemenetei, a sorokat pedig Bob bemenetei indexelik. $n=3$

EQ	000	001	010	011	100	101	110	111
000	egy	0	0	0	0	0	0	0
001	0	egy	0	0	0	0	0	0
010	0	0	egy	0	0	0	0	0
011	0	0	0	egy	0	0	0	0
100	0	0	0	0	egy	0	0	0
101	0	0	0	0	0	egy	0	0
110	0	0	0	0	0	0	egy	0
111	0	0	0	0	0	0	0	egy

Amint látjuk, a függvény csak azokban a cellákban egyenlő 1-gyel, ahol x egyenlő y -val (azaz az átlón). $\text{[math]}$

Tétel: $D(EQ)=n$

Bizonyíték. Tegyük fel , hogy , azaz létezik egy protokoll, amely megoldja az egyenlőség ellenőrzését az összes n hosszúságú bitsorpárra , miközben legfeljebb egy bitet továbbít. Írjuk ki egy sorba az azonos karakterláncok minden lehetséges párjához (azokhoz ) a protokollban elküldött összes bitet. Pontosan ilyen különálló párok vannak, és legfeljebb különböző hosszúságú bitsorok léteznek . A Dirichlet-elv szerint két és pár van , amelyekhez ugyanazokat a karakterláncokat kapjuk, vagyis ugyanazokat a biteket küldjük a protokollban. Mivel azon karakterláncpárok halmaza, amelyekhez ugyanazokat a biteket küldték, egy téglalapot határoz meg, akkor és egyenlőnek kell lennie 1-gyel is, ami ellentmond annak, hogy . Ezért a feltevésünk téves, ami azt jelenti $D(EQ)\leq n-1$ $n-1$ ${\megjelenítési stílus (x,x)}$ $EQ(x,x)=1$ ${\megjelenítési stílus (x,x)}$ $2^{n}$ $n-1$ ${\displaystyle 2+4+\dotsb +2^{n-1}=2^{n}-2<2^{n))$ ${\megjelenítési stílus (x,x)}$ $(x',x')$ $EQ(x,x')$ $EQ(x',x)$ $x\neq x'$ $D(EQ)>n-1$

Más szóval, ha kisebb, mint n , akkor az EQ mátrix mindegyikét le kell fednünk kevesebb egyszínű téglalappal (aminek minden cellája eggyel van megjelölve). Az EQ mátrixban azonban pontosan egyek vannak , és nem lehet kettő ugyanabban az egyszínű téglalapban, hiszen akkor a nullákkal jelölt cellák elkerülhetetlenül ebbe a téglalapba kerülnek. Ezért ilyen lefedettség nem létezik, és így legalább n . $D(EQ)$ $2^{n}$ $2^{n}$ $D(EQ)$

Jegyzetek

↑ Yao, AC (1979), Some Complexity Questions Related to Distributed Computing, Proc. 11. STOC 14. kötet: 209–213

Irodalom

Kushilevitz, Eyal; Nissan, NoamKommunikációs összetettség (határozatlan) . - Cambridge: Cambridge University Press , 2006. - ISBN 978-0-521-02983-4 .
Razborov A.A. A kommunikáció összetettsége . - MTSNMO, 2012. - 24 p. — ISBN 978-5-4439-0202-9 .
Verescsagin N.K., Shchepin E.V. Információ, kódolás és előrejelzés. - M. : FMOP, MTsNMO, 2012. - 238 p. - ISBN 978-5-94057-920-5 .

EQ	000	001	010	011	100	101	110	111
000	egy	0	0	0	0	0	0	0
001	0	egy	0	0	0	0	0	0
010	0	0	egy	0	0	0	0	0
011	0	0	0	egy	0	0	0	0
100	0	0	0	0	egy	0	0	0
101	0	0	0	0	0	egy	0	0
110	0	0	0	0	0	0	egy	0
111	0	0	0	0	0	0	0	egy

EQ	000	001	010	011	100	101	110	111
000	egy	0	0	0	0	0	0	0
001	0	egy	0	0	0	0	0	0
010	0	0	egy	0	0	0	0	0
011	0	0	0	egy	0	0	0	0
100	0	0	0	0	egy	0	0	0
101	0	0	0	0	0	egy	0	0
110	0	0	0	0	0	0	egy	0
111	0	0	0	0	0	0	0	egy

EQ	000	001	010	011	100	101	110	111
000	egy	0	0	0	0	0	0	0
001	0	egy	0	0	0	0	0	0
010	0	0	egy	0	0	0	0	0
011	0	0	0	egy	0	0	0	0
100	0	0	0	0	egy	0	0	0
101	0	0	0	0	0	egy	0	0
110	0	0	0	0	0	0	egy	0
111	0	0	0	0	0	0	0	egy