Algorytmiczny lemat lokalny Lovásza

W informatyce teoretycznej algorytmiczny lemat lokalny Lovásza podaje algorytmiczny sposób konstruowania obiektów podlegających systemowi ograniczeń o ograniczonej zależności.

Mając skończony zbiór złych zdarzeń { A ₁ , ..., A _n } w przestrzeni prawdopodobieństwa z ograniczoną zależnością między A _i s iz określonymi granicami ich odpowiednich prawdopodobieństw, lokalny lemat Lovásza dowodzi, że z niezerowym prawdopodobieństwem wszystkich tych zdarzeń można uniknąć. Jednak lemat jest niekonstruktywny, ponieważ nie daje żadnego wglądu w to, jak uniknąć złych zdarzeń.

Jeśli zdarzenia { A 1 , ..., An } są określone przez skończony zbiór wzajemnie niezależnych zmiennych losowych, prosty algorytm Las Vegas z oczekiwanym _{wielomianowym} czasem wykonania _Robina zaproponowany przez Mosera i Gábora Tardosa może obliczyć przypisanie do zmiennych losowych aby uniknąć wszystkich zdarzeń.

Przegląd lokalnego lematu Lovásza

Lokalny lemat Lovásza jest potężnym narzędziem powszechnie używanym w metodzie probabilistycznej do udowodnienia istnienia pewnych złożonych obiektów matematycznych o zbiorze określonych cech. Typowy dowód polega na operowaniu na złożonym obiekcie w sposób losowy i wykorzystuje lokalny lemat Lovásza do wyznaczenia prawdopodobieństwa braku którejkolwiek z cech. Brak cechy jest uważany za złe zdarzenie i jeśli można wykazać, że wszystkich takich złych zdarzeń można uniknąć jednocześnie z niezerowym prawdopodobieństwem, następuje istnienie. Sam lemat brzmi następująco:

Niech ${\ Displaystyle {\ mathcal {A}} = \ {A_ {1}, \ ldots, A_ {n} \}}$ będzie skończonym zbiorem zdarzeń w przestrzeni prawdopodobieństwa Ω. Dla $podzbiór$ $\ Displaystyle \ Gamma (A)}$ taki , że ZA ∈ $\ in {\ mathcal {A}}}$ ${\ Displaystyle A}$ jest niezależny od zbioru zdarzeń ${\ Displaystyle {\ mathcal {A}} \ setminus (\ {A \} \ kubek \ Gamma (A) )}$ . Jeśli istnieje przypisanie liczb rzeczywistych ${\ Displaystyle x: {\ mathcal {A}} \ rightarrow (0,1)}$ do zdarzeń takich, że

${\ Displaystyle \ forall A \ in {\ mathcal {A}}: \ Pr [A] \leq x(A)\prod _{B\in \Gamma (A)}(1-x(B))}$

wtedy prawdopodobieństwo uniknięcia wszystkich zdarzeń w jest dodatnie, w szczególności ${\ displaystyle {\ mathcal {A}}}$

${\ Displaystyle \ Pr \ lewo [\, {\ overline {A_ {1}}} \ klin \ cdots \ klin {\ overline {A_ {n}}} \, \ prawo] \ geq \ prod _ {A \ in {\mathcal {A}}}(1-x(A)).}$

Algorytmiczna wersja lokalnego lematu Lovásza

Lemat lokalny Lovásza jest niekonstruktywny, ponieważ pozwala nam jedynie stwierdzić istnienie właściwości strukturalnych lub obiektów złożonych, ale nie wskazuje, jak można je skutecznie znaleźć lub skonstruować w praktyce. Należy zauważyć, że losowe próbkowanie z przestrzeni prawdopodobieństwa Ω prawdopodobnie będzie nieefektywne, ponieważ prawdopodobieństwo zdarzenia będącego przedmiotem zainteresowania

{\ Displaystyle \ Pr \ lewo [{\ overline {A_ {1}}} \ klin \ cdots \ klin {\ overline {A_ {n}}} \ prawo]}

jest ograniczony tylko iloczynem małych liczb

{\ Displaystyle \ prod _ {A \ w {\ mathcal {A}}} (1-x (A))}

i dlatego prawdopodobnie będzie bardzo mały.

Zakładając, że wszystkie zdarzenia w $\$ określone przez skończony zbiór wzajemnie niezależnych zmiennych losowych w Ω, Robin Moser i P. $displaystyle {\ mathcal {P}}}$ Gábor Tardos zaproponował wydajny algorytm ${A}}} .$ , który oblicza przypisanie do zmiennych losowych w taki sposób, że unika się wszystkich zdarzeń w $mathcal$

W związku z tym algorytm ten może być używany do wydajnego konstruowania świadków złożonych obiektów o określonych cechach dla większości problemów, do których stosuje się lokalny lemat Lovásza.

Historia

Przed ostatnimi pracami Mosera i Tardosa, wcześniejsze prace również poczyniły postępy w opracowywaniu algorytmicznych wersji lokalnego lematu Lovásza. József Beck w 1991 roku po raz pierwszy udowodnił, że wersja algorytmiczna jest możliwa. W tym przełomowym wyniku na sformułowanie problemu nałożono surowsze wymagania niż w pierwotnej niekonstruktywnej definicji. Podejście Becka wymagało, aby dla każdego $liczba$ była powyżej przez ${\ Displaystyle |\ Gamma (A) | <2 ^ {n/48}}$ (w przybliżeniu). Egzystencjalna wersja lokalnego lematu pozwala na większą górną granicę zależności:

{\ Displaystyle |\ Gamma (A) | <{\ Frac {2 ^ {n}} {e}},}

Wiadomo, że ta granica jest ścisła. Od czasu powstania algorytmu wstępnego pracowano nad przybliżeniem algorytmicznych wersji lokalnego lematu do tej wąskiej wartości. Ostatnie prace Mosera i Tardosa są najnowszymi w tym łańcuchu i dostarczają algorytmu, który osiąga to ścisłe ograniczenie.

Algorytm

Wprowadźmy najpierw kilka pojęć, które są używane w algorytmie.

Dla dowolnej zmiennej losowej oznacza bieżące przypisanie (ocenę) $}, v_ {P}}$ { . Przypisanie (ocena) do wszystkich zmiennych losowych jest oznaczone ${\ Displaystyle (v_ {P}) _ {\ mathcal {P}}}$ .

Unikalny minimalny podzbiór zmiennych losowych w $A,$ który określa zdarzenie jest oznaczony przez vbl ( A ).

Jeśli zdarzenie A jest prawdziwe w ocenie ${\ Displaystyle (v_ {P}) _ {\ mathcal {P}}}$ , mówimy, że ${\ Displaystyle (v_ {P}) _{\mathcal {P}}}$ spełnia A , w przeciwnym razie unika A .

Biorąc pod uwagę zbiór złych zdarzeń, $chcemy$ uniknąć, a który jest określony przez zbiór wzajemnie niezależnych zmiennych losowych , algorytm postępuje w następujący sposób: ${\ displaystyle {\ mathcal {A}}}$ co następuje:

${\ Displaystyle \ forall P \ in {\ mathcal {P}}}$ : ${\ Displaystyle v_ {P} \ leftarrow}$ losowa ocena P.
${\ Displaystyle \ istnieje A \ in {\ mathcal {A}}}$ $\exists A\in {\mathcal {A}}$ ZA takie, że A jest spełnione przez $\ Displaystyle (v_ {P}) _ {\ mathcal {P}}}$ $(v_{P})_{{{\mathcal {P}}}}$
- wybrać dowolne spełnione zdarzenie ${\ Displaystyle A \ w {\ mathcal {A}}}$
- $_$ _ $_$ _
powrót ${\ Displaystyle (v_ {P}) _ {\ mathcal {P}}}$

W pierwszym kroku algorytm losowo inicjuje bieżące przypisanie v _P dla każdej zmiennej losowej ${\ displaystyle P \ in {\ mathcal {P}}}$ . Oznacza to, że przypisanie v _P jest próbkowane losowo i niezależnie zgodnie z rozkładem zmiennej losowej P .

Następnie algorytm wchodzi do głównej pętli, która jest wykonywana do momentu uniknięcia wszystkich zdarzeń w $iw$ którym momencie algorytm zwraca bieżące przypisanie W każdej iteracji głównej pętli algorytm wybiera dowolne spełnione zdarzenie A (losowo lub deterministycznie) i ponownie próbkuje wszystkie zmienne losowe, które określają A .

Główne twierdzenie

Niech $będzie$ zbiorem wzajemnie niezależnych zmiennych losowych w przestrzeni prawdopodobieństwa Ω. Niech $będzie$ zbiorem zdarzeń określonych przez te zmienne. Jeśli istnieje przypisanie liczb rzeczywistych do zdarzeń takich, że ${\ Displaystyle x: {\ mathcal {A}} \ do (0,1)}$

{\ Displaystyle \ forall A \ in {\ mathcal {A}}: \ Pr [A] \leq x(A)\prod _{B\in \Gamma (A)}(1-x(B))}

wtedy istnieje przypisanie wartości do zmiennych , $wszystkich$ zdarzeń $.$

Co więcej, opisany powyżej losowy algorytm ponownie próbkuje zdarzenie co najwyżej oczekiwane ${\ Displaystyle A \ in {\ mathcal {A}}}$

{\ Displaystyle {\ Frac {x (A)} {1-x (A)}}}

razy, zanim znajdzie taką ocenę. Zatem oczekiwana całkowita liczba kroków ponownego próbkowania, a tym samym oczekiwany czas działania algorytmu, wynosi co najwyżej

{\ Displaystyle \ suma _ {A \ w {\ mathcal {A}}} {\ Frac {x (A)} {1-x (A)}}.}

Dowód tego twierdzenia metodą kompresji entropii można znaleźć w artykule Mosera i Tardosa

Wersja symetryczna

Wymóg funkcji przypisania x spełniającej zbiór nierówności w powyższym twierdzeniu jest złożony i nie jest intuicyjny. Ale ten wymóg można zastąpić trzema prostymi warunkami:

${\ displaystyle \ forall A \ in {\ mathcal {A}}: |\ Gamma (A) | \ równoważnik D}$ , tj. każde zdarzenie A zależy od co najwyżej D innych zdarzeń,
${\ Displaystyle \ forall A \ in {\ mathcal {A}}: \ Pr [A] \ równoważnik p}$ , tj. prawdopodobieństwo każdego zdarzenia A wynosi co najwyżej p ,
${\ Displaystyle ep (D + 1) \ równoważnik 1}$ , gdzie e jest podstawą logarytmu naturalnego .

Wersja lokalnego lematu Lovásza z tymi trzema warunkami zamiast funkcji przypisania x jest nazywana symetrycznym lokalnym lematem Lovásza . Możemy również podać symetryczny algorytmiczny lokalny lemat Lovásza :

Niech będzie skończonym zbiorem wzajemnie niezależnych zmiennych losowych i $będzie$ skończonym zbiorem zdarzeń określonych przez te zmienne, $. Jeśli powyższe trzy warunki$ $.$ spełnione, to istnieje przypisanie wartości do zmiennych, $wszystkich$ zdarzeń w

Co więcej, opisany powyżej losowy algorytm ponownie próbkuje zdarzenie $A}}}$ najwyżej oczekiwane razy przed nim ${\ Displaystyle A \ in {\ mathcal$ znajduje taką ocenę. Zatem oczekiwana całkowita liczba kroków ponownego próbkowania, a tym samym oczekiwany czas działania algorytmu, wynosi co najwyżej ${\ displaystyle {\ frac {n} {D}}}$ .

Przykład

Poniższy przykład ilustruje, w jaki sposób algorytmiczna wersja lokalnego lematu Lovásza może zostać zastosowana do prostego problemu.

Niech Φ będzie formułą CNF nad zmiennymi X ₁ , ..., X _n , zawierającą n klauzul iz co najmniej k literałami w każdej klauzuli oraz z każdą zmienną X _i występującą najwyżej w ${\ Displaystyle { \frac {2^{k}}{ke}}}$ klauzule. Wtedy Φ jest spełnione.

Twierdzenie to można łatwo udowodnić za pomocą symetrycznej wersji algorytmicznego lokalnego lematu Lovásza. Niech X ₁ $,$ ..., X _n będzie zbiorem wzajemnie niezależnych zmiennych losowych które są próbkowane równomiernie losowo .

Po pierwsze, obcinamy każdą klauzulę w Φ, aby zawierała dokładnie k literałów. Ponieważ każda klauzula jest dysjunkcją, nie szkodzi to spełnialności, ponieważ jeśli uda nam się znaleźć satysfakcjonujące przypisanie dla skróconej formuły, można je łatwo rozszerzyć do satysfakcjonującego przypisania dla oryginalnej formuły poprzez ponowne wstawienie skróconych literałów.

Teraz zdefiniuj złe zdarzenie Aj _j dla każdej klauzuli w Φ, gdzie Aj _spełniona jest zdarzeniem, że klauzula w Φ nie jest przez bieżące przypisanie. Ponieważ każda klauzula zawiera k literałów (a zatem k zmiennych) i ponieważ wszystkie zmienne są próbkowane jednolicie losowo, możemy ograniczyć prawdopodobieństwo każdego złego zdarzenia przez

{\ Displaystyle \ Pr [A_ {j}] = p = 2 ^ {-k}.}

$,$ najwyżej w klauzulach aw każdej klauzuli jest k zmiennych, każde złe A zależeć _co najwyżej

{\ Displaystyle D = k \ lewo ({\ Frac {2 ^ {k}}} {ke}} -1 \ prawo) \ równoważnik {\ Frac {2^{k}}{e}}-1}

inne wydarzenia. Dlatego:

{\ Displaystyle D + 1 \ równoważnik {\ Frac {2 ^ {k}} {e}},}

mnożąc obie strony przez ep otrzymujemy:

{\ Displaystyle ep (D + 1) \ równoważnik e2 ^ {- k} {\ Frac {2 ^ {k}} {e}} = 1 }

z symetrycznego lokalnego lematu Lovásza wynika, że prawdopodobieństwo losowego przypisania do X ₁ , ..., X _n spełniającego wszystkie klauzule w Φ jest niezerowe, a zatem takie przypisanie musi istnieć.

Algorytmiczny Lemat Lokalny Lovásza faktycznie pozwala nam skutecznie obliczyć takie przypisanie, stosując algorytm opisany powyżej. Algorytm przebiega w następujący sposób:

Zaczyna się od losowego przypisania wartości prawdy do zmiennych X ₁ , ..., X _n próbkowanych jednostajnie losowo. Chociaż istnieje klauzula w Φ, która jest niespełniona, losowo wybiera ona niezaspokojoną klauzulę C w Φ i przypisuje nową wartość logiczną wszystkim zmiennym, które pojawiają się w C wybranych jednolicie losowo. Gdy wszystkie klauzule w Φ są spełnione, algorytm zwraca bieżące przypisanie. Stąd algorytmiczny lokalny lemat Lovásza dowodzi, że ten algorytm ma oczekiwany czas działania co najwyżej

{\ Displaystyle {\ Frac {n} {{\ Frac {2 ^ {k}} {e}} -k}}}

kroki na formułach CNF, które spełniają dwa powyższe warunki. Mocniejszą wersję powyższego twierdzenia potwierdza Moser, zob. także Berman, Karpiński i Scott.

Algorytm jest podobny do WalkSAT , który jest używany do rozwiązywania ogólnych logicznych problemów spełnialności . Główna różnica polega na tym, że w WalkSAT , po wybraniu niezaspokojonej klauzuli C , pojedyncza zmienna w C jest wybierana losowo i ma odwróconą wartość (co można postrzegać jako jednolity wybór tylko spośród tylko ${\ displaystyle k},$ a nie wszystkich ${\ Displaystyle 2 ^ {k}}$ przypisania wartości do do ).

Aplikacje

Jak wspomniano wcześniej, algorytmiczna wersja lokalnego lematu Lovásza ma zastosowanie do większości problemów, dla których ogólny lemat lokalny Lovásza jest używany jako technika dowodowa. Niektóre z tych problemów omówiono w następujących artykułach:

Wersja równoległa

Algorytm opisany powyżej dobrze nadaje się do zrównoleglenia, ponieważ ponowne próbkowanie dwóch niezależnych zdarzeń ${\ Displaystyle A, B \ in {\ mathcal {A}}}$ , tj. ${\ Displaystyle \ operatorname {vbl} (A) \ cap \ operatorname {vbl} (B) = \ pusty zestaw }$ równolegle jest równoważne ponownemu próbkowaniu A , B sekwencyjnie. Stąd w każdej iteracji głównej pętli można określić maksymalny zbiór niezależnych i spełnionych zdarzeń S i ponownie przepróbkować wszystkie zdarzenia w S równolegle.

Przy założeniu, że funkcja przypisania x spełnia nieco silniejsze warunki:

{\ Displaystyle \ forall A \ w {\ mathcal {A}}: \Pr[A]\leq (1-\varepsilon )x(A)\prod _{B\in \Gamma (A)}(1-x(B))}

dla pewnego ε > 0 Moser i Tardos udowodnili, że algorytm równoległy osiąga lepszą złożoność czasu wykonywania. W tym przypadku równoległa wersja algorytmu przyjmuje wartość oczekiwaną

{\ Displaystyle O \ lewo ({\ Frac {1} {\ varepsilon}} \ log \ suma _ {A \ w {\ mathcal {A}}}{\frac {x(A)}{1-x(A)}}\right)}

kroki, zanim się zakończy. Równoległa wersja algorytmu może być postrzegana jako szczególny przypadek algorytmu sekwencyjnego pokazanego powyżej, a więc ten wynik odnosi się również do przypadku sekwencyjnego.