Złożoność komunikacyjna

Prowadzący

Marcin Kotowski

Opis

"This is where, I think, language came from. I mean, it came from our desire to transcend our isolation and have some sort of connection with one another. It had to be easy when it was just simple survival. “Water.” We came up with a sound for that. “Sabretooth tiger right behind you!” We came up with a sound for that. But when it gets really interesting, I think, is when we use that same system of symbols to communicate all the abstract and intangible things that we’re experiencing."

(z filmu "Waking Life")

Złożoność komunikacyjna to dział informatyki teoretycznej zajmujący się ilością komunikacji potrzebnej do rozwiązywania różnych problemów obliczeniowych. Typowy setting jest następujący - Alicja i Bob dostają część danych wejściowych (odpowiednio x i y) i mają za zadanie obliczyć funkcję f zależącą od obu ciągów bitów (czyli f(x, y)). Interesuje nas, jak wiele komunikacji do tego potrzeba (zakładamy, że wszystkie inne obliczenia są darmowe, kosztuje jedynie przesyłanie informacji A->B i z powrotem). Teoria złożoności komunikacyjnej bada ograniczenia na ilość komunikacji, zarówno górne (konkretne protokoły) oraz dolne (i właściwie to te drugie stanowią "mięso" dziedziny).

Istniej sporo wariantów złożoności komunikacyjnej - deterministyczna, randomizowana z prywatną lub publiczną losowością, wieloosobowa etc. Techniki i rezultaty ze złożoności komunikacyjnej wykorzystuje się też m.in. w analizie obwodów boolowskich, drzew decyzyjnych i struktur danych, algorytmach strumieniowych i teorii informacji.

Zajęcia będą wprowadzeniem do dziedziny. Poznamy kilka podstawowych modeli komunikacji (gł. deterministyczny i randomizowany) oraz przykładowe problemy i techniki dowodenia dolnych ograniczeń. Pojawi się pewnie też o coś o zastosowaniach i być może zajawka o kwantowej złożoności komunikacyjnej. Zajęcia powinny być interesujące zarówno dla osób lubiących matematykę, jak i informatykę teoretyczną.

Program zajęć

Wymagania

Nie zakładam żadnej wiedzy wstępnej poza ogólnym obyciem z kombinatoryką i elementarnym rachunkiem prawdopodobieństwa - większość rzeczy będzie elementarna. Jeśli wśród uczestników będą osoby umiejace coś z algebry liniowej (np. z wiedzą, co to jest rząd macierzy), możemy rozszerzyć niektóre tematy.

Zadania kwalifikacyjne

Zadania należy przysyłać na adres: marcin.kotowski1@gmail.com do dnia 7 lipca. Jeśli macie jakieś wątpliwości, pytania, w zadaniach są niejasności etc. - piszcie. Zachęcam do przysyłania zadań wcześniej, można wtedy liczyć na możliwość ich poprawienia. Można też przysyłać rozwiązania częściowe. Nie ma ścisłego progu kwalifikującego na zajęcia - starajcie się zrobić tyle zadań, ile potraficie (w szczególności, nie trzeba robić ich wszystkich, by się zakwalifikować).

1. (Notacja asymptotyczna) Zapoznaj się z notacją asymptotyczną \(O(n), \Theta(n), \Omega(n)\) etc. Wprowadźmy na funkcjach \(f: \mathbb{N} \rightarrow \mathbb{N}\) porządek: \(f \leq g\), jeśli \(f(n) = O(g(n))\). Czy ten porządek jest liniowy? (tzn. czy dla dowolnych f,g, albo f≤g, albo g≤f?)

2. (Zagadka) W turnieju brało udział 16 drużyn. Alicja wie, jakie dwie drużyny grały w finale, ale nie spojrzała, która z nich wygrała. Bob wie, kto wygrał, ale z ekscytacji zapomniał, z kim grał zwycięzca. Ile bitów potrzebują wymienić Alicja i Bob, żeby Alicja dowiedziała się, kto wygrał?

3. (Rachunek prawdopodobieństwa)

 

a) Załóżmy, że mamy ciąg niezależnych rzutów monetą \(X_1, X_2, \dots, X_n, \dots\) każda z nich o prawdopodobieństwie wypadnięcia orła (=1) \(p\), a reszki (=0) \(1-p\) Co możemy powiedzieć o prawdopodobieństwie, że "empiryczna średnia" \(\frac{X_1 + \dots + X_n}{n}\) jest "blisko" wartości oczekiwanej \(X_i\), czyli \(p\)? (należy sensownie zdefiniować "blisko"; oczekuję jedynie podania oszacownia, niekoniecznie z dowodem - można posiłkować się Googlem/Wikipedią)

 

b) Powiedzmy, że wykonujemy pewne doświadczenie i otrzymujemy wynik 0 lub 1. Jeden z tych wyników jest "poprawny", ale nie wiemy który - wiemy tylko, że wynik będzie poprawny z prawdopodobieństwem \(p\). Chcemy zwiększyć to prawdopodobieńśtwo do \(1 - \varepsilon \) dla małego \(\varepsilon\), na przykład wykonując \(k(\varepsilon)\) niezależnych doświadczeń i jako wynik całej próby biorąc wynik, który pojawi się częściej. Jaka jest różnica w liczbie potrzebnych do tego prób między przypadkiem \(p=\frac{2}{3}\) a \(p = \frac{1}{2} + \frac{1}{2^n}\)? (gdzie \(n\) jest jakimś parametrem, od którego będzie zależeć odpowiedź)

 

c) Udowodnij dla nieujemnej zmiennej losowej \(X\) o średniej \(\mathbb{E}X\) nierówność: \(\mathbb{P}(X \geq t) \leq \frac{\mathbb{E}X}{t}\)

 

4. (Drzewa AND-OR) Drzewem AND-OR nazywamy pełne drzewo binarne wysokości n o następujących własnościach: a) w korzeniu drzewa umieszczona jest koniunkcja (AND); b) w synach korzenia umieszczona jest alternatywa (OR), i dalej na przemian AND i OR, aż do liści, w których umieszczone są wartości 0 lub 1 (tzn. poza liśćmi parzyste poziomy zawierają AND, a nieparzyste OR). Wartość drzewa wyliczamy rekurencyjnie: wartością węzła typu AND jest koniunkcja wartości jego poddrzew i analogicznie dla alternatywy. Załóżmy, że chcemy obliczyć wartość nieznanego drzewa, mogąc jedynie sprawdzać wartości w liściach wedle ustalonej kolejności (która może zależeć od wartości przeczytanych do tej pory).

 

a) ile, w najgorszym przypadku, potrzebujemy zapytań tej postaci, aby móc obliczyć wartość nieznanego drzewa? (należy założyć, że kiedy ustalimy już swój algorytm, drzewo jest wybierane przez adwersarza, który zna nasz algorytm i może dobrać wartości w liściach złośliwie)

 

b) co się zmieni, jeśli dopuścimy użycie losowości, tj. możemy wybierać liście do sprawdzenia losowo? (w tym wypadku należy powiedzieć coś np. o średniej liczbie zapytań potrzebnej, by uzyskać poprawną odpowiedż np. z prawdopodobieństwem >\(\frac{2}{3}\))

 

5. (Najczęściej występujący element) Wyobraźmy sobie, że czytamy kolejne elementy \(a_i\) ze "strumienia" długości \(m\). Każdy element jest liczbą ze zbioru \(\{0,1,...,n-1\}\). Chcemy znaleźć element występujący >\(\frac{m}{2}\) razy (o ile taki istnieje, w przeciwnym wypadku dajemy odpowiedź "żądany element nie istnieje"), zużywając do tego jak najmniej pamięci. Co można powiedzieć o ilości pamięci potrzebnej do tego zadania, jeśli: a) wiadomo z góry, że taki element istnieje, b) nie zakładamy nic o istnieniu takiego elementu?

6. (Obwody boolowskie) Obwodem boolowskim nazywamy skierowany acykliczny graf o następujących typach wierzchołków: a) zmienne \((x_1,x_2,...)\) lub ich negacje \((\bar{x_1},\bar{x_2},\dots)\); b) operatory logiczne (koniunkcja i alternatywa). Zakładamy, że istnieje dokładnie jeden wierzchołek wyjściowy (mający zero krawędzi wychodzących). Zmienne mają 0 krawędzi wchodzących i dowolnie dużo wychodzących, operatory logiczne mają dokładnie 2 krawędzie wchodzące i dowolnie dużo wychodzących (oczywiście poza wierzchołek wyjściowym). Zmienne przybierają wartości 0,1. Wartość logiczna obwodu jest określona naturalnie (wartość wierzchołka z alternatywą = alternatywa z wierzchołków wchodzących etc.).

 

a) Funkcja boolowska to po prostu funkcja \(f: \{0,1\}^n \rightarrow \{0,1\} \). Pokaż, że dla każdej funkcji \(f\) istnieje obwód (być może bardzo duży), który ją oblicza (tzn. taki, że wartość obwodu ze zmiennymi \(x_1,...,x_n\) wynosi \(f(x_1,...,x_n)\)).

 

b) Obwód nazwiemy monotonicznym, jeśli nie występują w nim negacje. Dla \(x,y \in \{0,1\}^n\) powiemy, że \(x \leq y\), jeśli dla każdego \(i\) mamy \(x_i \leq y_i\). Funkcję boolowską nazwiemy monotoniczną, jeśli \(x \leq y\) implikuje \(f(x) \leq f(y)\). Udowodnij, że funkcja obliczana przez obwód monotoniczny jest monotoniczna oraz że dla każdej funkcji monotonicznej istnieje obwód monotoniczny, który ją oblicza (uwaga: nie znaczy to, że nie może istnieć także obwód niemonotoniczny ją obliczający)

 

c) Pokaż, że "większość" funkcji boolowskich nie daje się obliczyć przy pomocy "małych" obwodów (należy sensownie zdefiniować oba pojęcia)

 

7. (Szukanie maksimum) Funkcję \(f:\{0,1,...,n-1\} \rightarrow \mathbb{R}\) nazwiemy unimodalną, jeśli istnieje dokładnie jeden taki element \(x\), że \(f\) jest ściśle rosnąca na lewo od \(x\) i ściśle malejąca na prawo od \(x\) (wobec tego \(x\) jest jedynym maksimum tej funkcji). Funkcję \(f \) możemy ewaluować w dowolnym punkcie \(y\), dostając w wyniku \(f(y)\).

a) Ile ewaluacji potrzeba do znalezienia maksimum (należy podać zarówno ograniczenie dolne, jak i algorytm osiągający to ograniczenie)? Odpowiedź podaj w notacji \(O(\cdot)\) (tzn. nie interesują nas stałe, np. ograniczenie typu "co najmniej g(n) i co najwyżej 100 * g(n)" jest OK)

b) (trudniejsze) To samo, co w a), ale podaj odpowiedź dokładną (tj. z optymalną stałą)

8. (Własności grafów i ciągów)

a) Własność ciągu bitów nazwiemy trudną dla długości \(n\), jeśli stwierdzenie, czy dany na wejściu ciąg bitów długości \(n\) posiada tę własność, wymaga, w najgorszym przypadku, obejrzenia wszystkich \(n\) bitów. Na przykład własność "ciąg zawiera co najmniej jedną jedynkę" jest trudna dla dowolnego \(n\). Pokaż, że własność "ciąg zawiera w którymś miejscu trzy jedynki pod rząd" jest trudna dla danego n wtedy i tylko wtedy, gdy \(n=0\) lub \(n=3\) modulo \(4\)

b) Własność grafu skierowanego nazwiemy trudną dla \(n\) wierzchołków, jeśli stwierdzenie, czy dany na wejściu graf skierowany o \(n\) wierzchołkach posiada tę własność, wymaga, w najgorszym przypadku, obejrzenia wszystkich \(n(n-1)\) potencjalnych krawędzi (tzn. możemy zapytać o uporządkowaną parę wierzchołków \((u,v)\) i dowiedzieć się, czy istnieje między nimi skierowana krawędź). Ściekiem w grafie skierowanym o \(n\) wierzchołkach nazwiemy wierzchołkem, do którego wchodzi \(n-1\) i nie wychodzi żadna krawędź. Czy własność "graf posiada ściek" jest trudna?

c) (znacznie trudniejsze) Własność grafów (skierowanych lub nie) nazwiemy monotoniczną, jeśli zachodzi wynikanie: jeśli graf \(G\) posiada daną własność, to graf otrzymany z \(G\) przez dodawanie krawędzi też ją posiada. Przykładami własności monotonicznych są spójność lub nieplanarność, a przykładem własności niemonotonicznej grafu skierowanego - posiadanie ścieku (p. punkt b)). Co można powiedzieć o ilości zapytań potrzebnych do stwierdzenia, czy graf posiada daną monotoniczną własność? Czy wszystkie monotoniczne własności są trudne?