Složitost komunikace

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 30. prosince 2019; ověření vyžaduje 1 úpravu .

V teoretické informatice komplexnost komunikace studuje množství komunikace potřebné k vyřešení problému, jehož parametry jsou sdíleny dvěma nebo více stranami. Tento pojem zavedl Andrew Yao v roce 1979 [1] , který zkoumal následující problém pro dva účastníky, tradičně nazývané Alice a Bob . Alice obdrží n - bitový řetězec x a Bob n - bitový řetězec y a jejich cílem je, aby jeden z nich (například Bob) vypočítal funkci definovanou a známou oběma stranám , s co nejmenším množstvím komunikace mezi nimi . . Samozřejmě mohou vždy počítat takto: Alice pošle celý svůj n-bitový řetězec Bobovi, který pak vyhodnotí funkci . Proto je v této formulaci problému zajímavé, pro které funkce f existuje způsob, jak vypočítat přenosem méně než n bitů. Je důležité si uvědomit, že v tomto problému nás nezajímá složitost výpočtů provedených Alicí nebo Bobem, ani velikost paměti použité pro tyto výpočty. $f(x,y)$ $f(x,y)$ $f(x,y)$ $f(x,y)$

Tento abstraktní problém dvou účastníků (nazývaný složitost komunikace dvou účastníků) a jeho obecná podoba s mnoha účastníky vyvstává v různých oblastech informatiky: například při návrhu velkých integrovaných obvodů je potřeba minimalizovat spotřebu energie snížením počet elektrických signálů mezi různými součástmi během distribuovaného výpočtu. Komunikační složitost se využívá také při studiu datových struktur a algoritmů, při optimalizaci počítačových sítí, v teorii výpočetní složitosti a důkazové složitosti a v dalších oblastech.

Formální definice

Nechť je zpočátku uvedena nějaká funkce , kde v nejtypičtějším příkazu . Alice dostane , Bob dostane . Tím, že si Alice a Bob vyměňují zprávy po jednotlivých bitech (pomocí nějakého předem určeného komunikačního protokolu ), chtějí vypočítat hodnotu tak, aby na konci komunikace alespoň jeden z nich hodnotu znal . $f:X\krát Y\to Z$ $X=Y=\{0,1\}^{n},Z=\{0,1\}$ $x\in X$ $y\v Y$ $z=f(x,y)$ $z$

Komunikační složitost výpočtu funkce $F$ , označovaná , je definována jako minimální počet komunikačních bitů, který postačuje k vyřešení problému v nejhorším případě (to znamená, že tento počet bitů by měl stačit pro libovolný pár ). $D(f)$ $x, y$

Na základě této definice je vhodné uvažovat o funkci f jako o funkci dané maticí A , ve které jsou řádky indexovány elementy a sloupce elementy . V každé buňce této matice, indexované prvky x a y , je zapsána odpovídající hodnota f , tedy . Alice a Bob znají funkci f a proto znají matici A . Dále dostane Alice číslo řádku x a Bob číslo sloupce y a jejich úkolem je určit hodnotu zapsanou v odpovídající buňce. Pokud tedy v určité chvíli jeden z hráčů zná číslo sloupce i číslo řádku zároveň, pak bude znát i hodnotu v odpovídající buňce. Na začátku komunikace každý hráč neví nic o čísle druhého hráče, takže z pohledu Alice může být odpovědí jakákoliv hodnota v řádku x a z pohledu Boba jakákoliv hodnota ve sloupci y . . V procesu komunikace s každým přenášeným bitem se objevují nové informace, které hráčům umožňují odříznout některé z možných buněk. Pokud například v určitém okamžiku Alice přenese bit b , pak z Bobova pohledu jsou všechny možné vstupy Alice v tom okamžiku rozděleny do dvou sad: ty, pro které by Alice poslala , a ty, pro které by Alice poslala . Bob, který zná hodnotu bitu b , odřízne některé z Aliciných možných vstupů a zúží tak množinu možných buněk ze svého pohledu. V tomto případě se z pohledu vnějšího pozorovatele po každé zprávě zúží buď množina možných řádků nebo množina možných sloupců a tím se zúží množina možných buněk o nějakou podmatici matice A . $x\in X$ $y\v Y$ $A_{\mathrm {x,y} }=f(x,y)$ $b=0$ $b=1$

Formálněji budeme množinu nazývat (kombinatorický) obdélník , pokud to vyplývá z toho , že a . Potom je každá podmatice matice A spojena s kombinatorickým obdélníkem R tak, že , kde a . Nyní zvažte situaci, kdy již bylo mezi účastníky přeneseno k bitů. Nechť těchto prvních k bitů je dáno řetězcem . Pak je možné definovat množinu párů vstupů , na kterých se první k rovnají $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

- komunikační bit na vstupech je roven

(x,y)

h\}

Pak je kombinatorický obdélník, to znamená, že definuje podmatici matice A . $T_{\mathrm {h} }$

Příklad: Funkce EQ

Nechte _ Zvažte problém, ve kterém Alice a Bob chtějí zjistit, zda mají stejné řetězce, to znamená, že chtějí zkontrolovat, že . Je snadné ukázat, že k vyřešení tohoto problému testu rovnosti (EQ) potřebujeme v nejhorším případě přenést n bitů, pokud chceme na tuto otázku odpovědět přesně pro všechny možné dvojice x a y . $X=Y=\{0,1\}^{n},Z=\{0,1\}$ $x=y$

Pro případ se řetězce x a y skládají ze tří bitů. Funkce rovnosti je v tomto případě definována následující maticí, kde řádky jsou indexovány vstupy Alice a řádky jsou indexovány vstupy Boba. $n=3$

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

Jak vidíme, funkce je rovna 1 pouze v buňkách, kde x je rovno y (tedy na diagonále). $\text{[math]}$

Věta: $D(EQ)=n$

Důkaz. Předpokládejme , že existuje protokol, který řeší problém kontroly rovnosti pro všechny páry bitových řetězců délky n , přičemž nepřenáší více než bit. Vypišme pro každou možnou dvojici shodných řetězců (pro ně ) do řádku všechny bity, které byly odeslány v protokolu. Přesně takové odlišné páry existují a existují nanejvýš odlišné bitové řetězce délky . Podle Dirichletova principu existují dva páry a , pro které jsou získány stejné řetězce, to znamená, že v protokolu byly odeslány stejné bity. Protože množina párů řetězců, pro které byly odeslány stejné bity, definuje obdélník, pak a musí být také rovno 1, což je v rozporu se skutečností, že . Náš předpoklad je tedy chybný, což znamená $D(EQ)\leq n-1$ $n-1$ $(x,x)$ $EQ(x,x)=1$ $(x,x)$ $2^{n}$ $n-1$ ${\displaystyle 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$

Jinými slovy, pokud je menší než n , pak bychom měli být schopni pokrýt všechny jedničky matice EQ méně jednobarevnými obdélníky (jejichž všechny buňky jsou označeny jedničkami). V matici EQ jsou však přesně jedničky a žádné dvě nemohou ležet ve stejném jednobarevném obdélníku, protože buňky označené nulami nevyhnutelně spadnou do tohoto obdélníku. Proto takové pokrytí neexistuje, a tedy alespoň n . $D(EQ)$ $2^{n}$ $2^{n}$ $D(EQ)$

Poznámky

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

Literatura

Kushilevitz, Eyal; Nissan, NoameKomunikační složitost (neurčitá) . - Cambridge: Cambridge University Press , 2006. - ISBN 978-0-521-02983-4 .
Razborov A.A. Komunikační složitost . - MTSNMO, 2012. - 24 s. — ISBN 978-5-4439-0202-9 .
Vereshchagin N.K., Shchepin E.V. Informace, kódování a predikce. - M. : FMOP, MTsNMO, 2012. - 238 s. - ISBN 978-5-94057-920-5 .