Complexitatea comunicării

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 decembrie 2019; verificarea necesită 1 editare .

În informatica teoretică , complexitatea comunicării studiază cantitatea de comunicare necesară pentru a rezolva o problemă ai cărei parametri sunt împărtășiți între două sau mai multe părți. Această noțiune a fost introdusă de Andrew Yao în 1979 [1] , care a investigat următoarea problemă pentru doi participanți, numiți în mod tradițional Alice și Bob . Alice primește un șir de n biți x și Bob un șir de n biți y , iar scopul lor este ca unul dintre ei (de exemplu, Bob) să calculeze o funcție definită și cunoscută de ambele părți , cu cea mai mică cantitate de comunicare între ele . Desigur, ei pot calcula întotdeauna astfel: Alice îi trimite întregul șir de n biți lui Bob, care apoi evaluează funcția . Prin urmare, în această formulare a problemei, este interesant pentru ce funcții f există o modalitate de a calcula prin transmiterea mai puțin de n biți. Este important de menționat că în această problemă nu ne interesează complexitatea calculelor efectuate de Alice sau Bob, sau dimensiunea memoriei utilizate pentru aceste calcule. $f(x,y)$ $f(x,y)$ $f(x,y)$ $f(x,y)$

Această problemă abstractă cu doi participanți (numită complexitate a comunicării cu doi participanți) și forma ei generală cu mulți participanți apare în diferite domenii ale informaticii: de exemplu, în proiectarea circuitelor integrate mari , necesitatea de a minimiza energia utilizată prin reducerea numărul de semnale electrice între diferite componente în timpul calculului distribuit. Complexitatea comunicării este utilizată și în studiul structurilor de date și al algoritmilor, în optimizarea rețelelor de calculatoare, în teoria complexității computaționale și a complexității probei și în alte domenii.

Definiție formală

Să fie dată inițial o anumită funcție , unde în declarația cea mai tipică . Alice primește , Bob primește . Schimbând mesaje unul cu celălalt pe rând (folosind un protocol de comunicare predeterminat ), Alice și Bob vor să calculeze valoarea astfel încât la sfârșitul comunicării cel puțin unul dintre ei să cunoască valoarea . $f:X\time Y\to Z$ $X=Y=\{0,1\}^{n},Z=\{0,1\}$ $x\în X$ $y\în Y$ $z=f(x,y)$ $z$

Complexitatea de comunicare a calculării funcției $f$ , notată cu , este definită ca numărul minim de biți de comunicare care este suficient pentru a rezolva problema în cel mai rău caz (adică acest număr de biți ar trebui să fie suficient pentru orice pereche de ). $D(f)$ $X y$

Pe baza acestei definiții, este convenabil să ne gândim la funcția f ca la o funcție dată de matricea A , în care rândurile sunt indexate prin elemente , iar coloanele, respectiv, pe elemente . În fiecare celulă a acestei matrice, indexată de elementele x și y , se scrie valoarea corespunzătoare a lui f , adică . Alice și Bob cunosc funcția f și, prin urmare, cunosc matricea A . Apoi, Alicei i se dă numărul de rând x , iar lui Bob numărul coloanei y , iar sarcina lor este să determine valoarea scrisă în celula corespunzătoare. Prin urmare, dacă la un moment dat unul dintre jucători știe atât numărul coloanei, cât și numărul liniei în același timp, atunci va ști și valoarea din celula corespunzătoare. La începutul comunicării, fiecare jucător nu știe nimic despre numărul celuilalt jucător, așa că din punctul de vedere al lui Alice, răspunsul poate fi orice valoare din rândul x , iar din punctul de vedere al lui Bob, orice valoare din coloana y . În procesul de comunicare cu fiecare bit transmis, apar informații noi, care le permit jucătorilor să taie unele dintre celulele posibile. De exemplu, dacă la un moment dat Alice transmite bitul b , atunci din punctul de vedere al lui Bob, toate intrările posibile ale lui Alice până în acel moment sunt împărțite în două seturi: cele pentru care Alice ar trimite și cele pentru care Alice ar trimite . Cunoscând valoarea bitului b , Bob întrerupe unele dintre posibilele intrări ale lui Alice și astfel restrânge setul de posibile celule din punctul său de vedere. În acest caz, din punctul de vedere al unui observator extern, după fiecare mesaj, fie setul de rânduri posibile, fie setul de coloane posibile este restrâns și astfel setul de celule posibile este restrâns de vreo submatrice a matricei A . $x\în X$ $y\în Y$ $A_{\mathrm {x,y} }=f(x,y)$ $b=0$ $b=1$

Mai formal, vom numi o mulțime numită dreptunghi (combinatorial) dacă rezultă din faptul că și . Atunci fiecare submatrice a matricei A este asociată cu un dreptunghi combinatoriu R astfel încât , unde și . Acum luați în considerare situația când k biți au fost deja transferați între participanți. Fie acești primi k biți dați de șirul . Apoi este posibil să se definească un set de perechi de intrări pe care primele k sunt egale $R\subseteq X\time Y$ $(x_{1},y_{1})\in R$ $(x_{2},y_{2})\în R$ $(x_{1},y_{2})\in R$ $(x_{2},y_{1})\in R$ $R=M\times N$ $M\subseteq X$ $N\subseteq Y$ $h\in \{0,1\}^{k)$ $T_{\mathrm {h} }\subseteq X\times Y$ $h$

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

- bitul de comunicare la intrări este egal cu

(x,y)

h\}

Atunci este un dreptunghi combinatoriu, adică definește o submatrice a matricei A . ${\displaystyle T_{\mathrm {h} ))$

Exemplu: funcția EQ

Lasă . Luați în considerare o problemă în care Alice și Bob vor să determine dacă li se dau aceleași șiruri, adică vor să verifice că . Este ușor să arătăm că pentru a rezolva această problemă a testului de egalitate (EQ) , trebuie să transmitem n biți în cel mai rău caz, dacă dorim să putem răspunde la această întrebare exact pentru toate perechile posibile de x și y . $X=Y=\{0,1\}^{n},Z=\{0,1\}$ $x=y$

Pentru cazuri, șirurile x și y constau din trei biți. Funcția de egalitate în acest caz este definită de următoarea matrice, unde rândurile sunt indexate de intrările lui Alice și rândurile sunt indexate de intrările lui Bob. $n=3$

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

După cum putem vedea, funcția este egală cu 1 numai în celulele în care x este egal cu y (adică pe diagonală). $\text{[math]}$

Teorema: $D(EQ)=n$

Dovada. Să presupunem că , adică există un protocol care rezolvă problema verificării egalității pentru toate perechile de șiruri de biți de lungime n , în timp ce nu transmite mai mult de un bit. Să scriem pe o linie pentru fiecare pereche posibilă de șiruri identice (pentru ei ) toți biții care au fost trimiși în protocol. Există exact astfel de perechi distincte și există cel mult șiruri de biți distincte de lungime . Conform principiului Dirichlet , există două perechi și , pentru care se obțin aceleași șiruri, adică aceiași biți au fost trimiși în protocol. Deoarece setul de perechi de șiruri pentru care au fost trimiși aceiași biți definește un dreptunghi, atunci și trebuie să fie, de asemenea, egal cu 1, ceea ce contrazice faptul că . Prin urmare, presupunerea noastră este greșită, ceea ce înseamnă $D(EQ)\leq n-1$ $n-1$ $(x,x)$ $EQ(x,x)=1$ $(x,x)$ $2^{n}$ $n-1$ $2+4+\dotsb +2^{n-1}=2^{n}-2<2^{n)$ $(x,x)$ $(x',x')$ $EQ(x,x')$ $EQ(x',x)$ $x\neq x'$ $D(EQ)>n-1$

Cu alte cuvinte, dacă este mai mic de n , atunci ar trebui să putem acoperi toate cele ale matricei EQ cu mai puține dreptunghiuri cu o singură culoare (din care toate celulele sunt marcate cu unele). Cu toate acestea, există exact unele în matricea EQ și nici două nu pot sta în același dreptunghi cu o singură culoare, deoarece atunci celulele marcate cu zerouri vor cădea inevitabil în acest dreptunghi. Prin urmare, o astfel de acoperire nu există și, prin urmare, cel puțin n . $D(EQ)$ $2^{n}$ $2^{n}$ $D(EQ)$

Note

↑ Yao, AC (1979), Some Complexity Questions Related to Distributed Computing, Proc. din al 11-lea STOC vol . 14: 209–213

Literatură

Kushilevitz, Eyal; Nissan, NoamComplexitatea comunicării (nedefinită) . - Cambridge: Cambridge University Press , 2006. - ISBN 978-0-521-02983-4 .
Razborov A.A. Complexitatea comunicării . - MTSNMO, 2012. - 24 p. — ISBN 978-5-4439-0202-9 .
Vereshchagin N.K., Shchepin E.V. Informare, codificare și predicție. - M. : FMOP, MTsNMO, 2012. - 238 p. - ISBN 978-5-94057-920-5 .

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

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

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