Lema locală algoritmică Lovas

Lema locală algoritmică Lovas este o lemă în informatica teoretică care permite construirea unor obiecte supuse anumitor restricții.

Din lema locală Lovas rezultă că probabilitatea ca niciunul dintre evenimentele dintr-un set de evenimente „rele” să nu se producă este strict pozitivă dacă aceste evenimente satisfac unele restricții suplimentare. În același timp, lema nu este constructivă și nu permite să construim în mod explicit exemple de obiecte pentru care aceste evenimente nu au loc. În cazul în care aceste evenimente sunt determinate de un set finit de variabile aleatoare independente unele de altele, algoritmul de tip Las Vegas cu timp de rulare polinomial dezvoltat de oamenii de știință Robin Moser și Gabor Tardos vă permite să calculați în mod explicit un anumit set . de valori ale acestor variabile, pentru care nu există niciunul dintre evenimentele aleatoare considerate [1] . $\{A_{1},\dots, A_{n}\}$

O privire de ansamblu asupra lemei locale Lovas

Lema locală Lovas este un instrument puternic folosit în mod obișnuit în metodele probabilistice pentru a demonstra existența unor obiecte matematice complexe cu un set de caracteristici date. O demonstrație tipică se rezumă la luarea în considerare a proprietăților unui obiect din punctul de vedere al teoriei probabilităților și utilizarea lemei locale Lovas pentru a estima probabilitatea absenței oricăreia dintre caracteristici. Absența unui semn este considerată un eveniment „rău”, iar dacă se poate demonstra că toate astfel de evenimente „rele” pot fi evitate în același timp, atunci se dovedește existența obiectului. Lema în sine este formulată după cum urmează:

Fie un set finit de evenimente în spațiul probabilității . Pentru orice , să determinăm vârfurile adiacente vârfului în graficul de dependență (în graficul de dependență, vârful este adiacent evenimentelor de care nu este independent). Dacă există o mapare astfel încât ${\mathcal {A}}=\{A_{1},\ldots ,A_{n}}\}$ $\Omega$ $A\in {\mathcal {A}}$ $\Gamma (A)$ $A$ $A$ $x:{\mathcal {A}}\la (0,1)$

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

atunci probabilitatea ca niciunul dintre evenimente să nu se producă este pozitivă și anume ${\mathcal {A}}$

\Pr \left({\overline {A_{1)}}\wedge \cdots \wedge {\overline {A_{n}}}\right)\geq \prod \limits _{i\in \{ 1,\dots ,n\}}(1-x(A_{i})).

O versiune algoritmică a lemei locale a lui Lovas

Lema locală a lui Lovas este neconstructivă deoarece permite să se deducă existența proprietăților structurale sau a obiectelor complexe, dar nu indică modul în care se poate găsi sau construi eficient în practică. În acest caz, eșantionarea aleatorie din spațiul probabilității este probabil să fie ineficientă, deoarece probabilitatea evenimentului de interes este $\Omega$

\Pr \left({\overline {A_{1)}}\wedge \cdots \wedge {\overline {A_{n)}}\right)

limitat doar de produsul unor cantitati mici

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

și, prin urmare, este probabil să fie foarte mic.

Presupunând că toate evenimentele de la sunt determinate de un set finit de variabile aleatoare reciproc independente de la , Robin Moser și Gabor Tardos au propus un algoritm aleator eficient care găsește un set de variabile aleatoare astfel încât toate evenimentele de la să nu fie valabile. ${\mathcal {A}}$ ${\mathcal {P}}$ $\Omega$ ${\mathcal {P}}$ ${\mathcal {A}}$

Prin urmare, acest algoritm poate fi folosit pentru a construi eficient obiecte complexe cu caracteristici prescrise pentru majoritatea problemelor la care se aplică lema locală Lovas.

Istorie

Lucrarea lui Moser și Tardos a fost precedată de alte rezultate care au condus la progrese în dezvoltarea versiunilor algoritmice ale lemei locale a lui Lovas. În 1991 , Joseph Beck a arătat pentru prima dată că este posibil, în principiu, să se dezvolte o versiune algoritmică a lemei [2] . În lucrarea sa, formularea lemei a fost mai riguroasă decât în definiția originală neconstructivă. Abordarea lui Beck a cerut ca pentru fiecare , numărul de dependențe să fie mărginit de sus ca . Versiunea neconstructivă a lemei locale admite o constrângere mai slabă: $A\in {\mathcal {A}}$ $A$ $|\Gamma (A)|<2^{\frac {n}{48}}$

|\Gamma (A)|<{\frac {2^{n}}{e}}.

Această estimare nu poate fi îmbunătățită. Lucrările ulterioare au schimbat treptat această estimare până când Moser și Tardos au prezentat un algoritm care o realizează.

În 2020, Robin Moser și Gabor Tardos au primit Premiul Gödel pentru o versiune algoritmică a lemei locale a lui Lovas [3] [4] .

Algoritm

Fie realizarea curentă a variabilei aleatoare și fie realizarea tuturor variabilelor aleatoare din . $v_{P}$ $P\in {\mathcal {P)}$ $(v_{P})_{\mathcal {P)}$ ${\mathcal P}$

Subsetul minim unic de variabile aleatoare care determină dacă va avea loc un eveniment este notat cu . ${\mathcal {P}}$ $A$ ${\text{vbl}}(A)$

Dacă evenimentul este adevărat în timpul evaluării , spunem că evaluarea satisface , altfel evită . $A$ $(v_{P})_{\mathcal {P)}$ $(v_{P})_{\mathcal {P)}$ $A$ $A$

Algoritmul funcționează astfel:

Pentru fiecare valoare , calculați aleatoriu o parte din implementarea acesteia $P\in {\mathcal {P)}$ $v_{P}$
Atâta timp cât există unul care să satisfacă : $A\in {\mathcal {A}}$ $(v_{P})_{\mathcal {P)}$ $A$
- Selectați un eveniment satisfăcut arbitrar $A\in {\mathcal {A}}$
- Pentru fiecare cantitate , calculați o nouă realizare $P\in {\text{vbl}}(A)$ $v_{P}$
Întoarcere $(v_{P})_{\mathcal {P)}$

În prima etapă, algoritmul inițializează aleatoriu alocarea curentă pentru fiecare variabilă aleatoare . Aceasta înseamnă că valoarea este aleasă aleatoriu și independent în funcție de distribuția variabilei aleatoare . Apoi algoritmul intră în bucla principală, care este executată până când este găsită implementarea dorită. La fiecare iterație a buclei principale, algoritmul selectează un eveniment satisfăcut arbitrar și reslectează toate variabilele aleatoare care determină . $v_{P}$ $P\in {\mathcal {P)}$ $v_{P}$ $P$ ${\mathcal {A}}$ ${\mathcal {A}}$

Teorema principală

Fie o mulțime finită de variabile aleatoare independente în totalitatea spațiului de probabilitate , fie o mulțime finită de evenimente determinate de aceste variabile. Dacă există un set astfel încât ${\mathcal {P}}$ $\Omega$ ${\mathcal {A}}$ $x:{\mathcal {A}}\la (0,1)$

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

apoi există o implementare care evită toate evenimentele din . În plus, algoritmul randomizat descris mai sus reselege cel mult un eveniment ${\mathcal {P}}$ ${\mathcal {A}}$ $A\in {\mathcal {A}}$

{\frac {x(A)}{1-x(A)))

ori înainte de a găsi implementarea necesară. Astfel, timpul de execuție așteptat al algoritmului nu depășește

\sum _{A\in {\mathcal {A}}}{\frac {x(A)}{1-x(A)))

[1] .

Versiune simetrică

Cerințele pot părea complexe și neintuitive. Dar poate fi înlocuit cu trei condiții simple: $x$

$\forall A\in {\mathcal {A):|\Gamma (A)|\leq D$ , adică fiecare eveniment depinde de nu mai mult decât de alte evenimente; $A$ $D$
$\forall A\in {\mathcal {A}}:\Pr(A)\leq p$ , adică probabilitatea fiecărui eveniment nu depășește ; $A$ $p$
$ep(D+1)\leq 1$ , unde este baza logaritmului natural al lui . $e$

O variantă a lemei locale Lovas cu aceste trei condiții în loc de o mulțime se numește lema locală Lovas simetrică. De asemenea, este posibil să se formuleze lema Lovas algoritmică locală simetrică: $x$

Fie un set finit de variabile aleatoare reciproc independente și un set finit de evenimente determinate de aceste variabile. Dacă sunt îndeplinite cele trei condiții de mai sus, atunci există o realizare a valorilor din care evită toate evenimentele din . În plus, algoritmul randomizat descris mai sus reselege un eveniment nu mai mult de o dată înainte de a găsi acea realizare. Astfel, timpul total de execuție așteptat al algoritmului nu depășește . ${\mathcal {P}}$ $\mathcal{A}$ ${\mathcal {P}}$ ${\mathcal {A}}$ $A\in {\mathcal {A}}$ ${\frac {1}{D)}$ ${\frac {n}{D)}$

Exemplu

Următorul exemplu arată cum o versiune algoritmică a lemei locale a lui Lovas poate fi aplicată unei probleme simple.

Fie o formă normală conjunctivă a unei formule peste variabile care conțin clauze și care au cel puțin literale în fiecare clauză, iar fiecare variabilă este prezentă în cel mult clauze. Atunci realizabil . $\Phi$ $X_{1},\dots ,X_{n}$ $n$ $k$ $X_{i}$ ${\frac {2^{k}}{ke}}$ $\Phi$

Această afirmație poate fi demonstrată folosind o versiune simetrică a lemei locale algoritmice a lui Lovas. Fie un set de variabile aleatoare independente , care sunt alese uniform și independent unele de altele . Fără pierderea generalității, putem presupune că există exact literali în fiecare propoziție. Evenimentul „rău” din această sarcină este evenimentul corespunzător faptului că clauza --a nu este îndeplinită. Deoarece fiecare clauză conține literale (și, prin urmare, variabile) și toate variabilele sunt alese aleatoriu, putem estima probabilitatea fiecărui eveniment „rău” după cum urmează: $X_{1},\dots ,X_{n}$ ${\mathcal {P}}$ $k$ $A_{i}$ $i$ $k$ $k$

\Pr(A_{i})=p=2^{-k}.

Deoarece fiecare variabilă poate apărea în cel mult clauze și în fiecare clauză de variabile, fiecare eveniment „rău” poate depinde de cel mult ${\frac {2^{k}}{ke}}$ $k$ $A_{i}$

D=k\left({\frac {2^{k}}{ke}}-1\right)\leq {\frac {2^{k}}{e}}-1

alte evenimente, deci

D+1\leq {\frac {2^{k}}{e}}.

Dacă înmulțiți ambele părți cu , obțineți $ep$

ep(D+1)\leq e2^{-k}{\frac {2^{k}}{e}}=1

Din lema locală simetrică Lovas rezultă că probabilitatea unei realizări sub care toate clauzele sunt satisfăcute nu este zero și, prin urmare, o astfel de realizare trebuie să existe. Lema algoritmică a lui Lovas permite ca o astfel de atribuire să fie găsită într-un timp rezonabil folosind algoritmul descris mai sus. Algoritmul funcționează astfel: $X_{1},\dots ,X_{n}$ $\Phi$

Inițial, este luată o implementare aleatorie . Până când întreaga formulă devine adevărată, o clauză nesatisfăcută din este selectată aleatoriu și apoi tuturor variabilelor care apar în li se atribuie noi valori, care sunt alese uniform la întâmplare. Odată ce toate clauzele de la sunt satisfăcute, algoritmul returnează implementarea curentă. Prin urmare, lema locală algoritmică a lui Lovas demonstrează că acest algoritm va rula cel mult $X_{1},\dots ,X_{n}$ $\Phi$ $C$ $\Phi$ $C$ $\Phi$

{\frac {n}{{\frac {2^{k}}{e}}-k}}

pași pe formule care îndeplinesc cele două condiții de mai sus. O versiune mai puternică a afirmației de mai sus a fost dovedită de Moser [5] , vezi și Birman, Karpinski și Scott [6] .

Versiune paralelă

Algoritmul descris mai sus este foarte potrivit pentru paralelizare, deoarece generarea paralelă de noi implementări pentru evenimente astfel încât , este echivalentă cu generarea secvențială. Prin urmare, la fiecare iterație a buclei principale, este posibil să se determine setul maxim de evenimente independente satisfăcute și să se regenereze toate evenimentele în paralel. $A,B\in {\mathcal {A}}$ ${\text{vbl}}(A)\cap {\text{vbl}}(B)=\emptyset$ $S$ $S$

Dacă setul îndeplinește condiții puțin mai stricte: $X$

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

pentru unii , atunci algoritmul paralel oferă timpul de execuție așteptat al ordinului $\varepsilon >0$

O\left({\frac {1}{\varepsilon }}\log \sum _{A\in {\mathcal {A}}}{\frac {x(A)}{1-x(A) )}}\dreapta)

Note

↑ 1 2 Moser, Robin A.; Tardos, Gabor. O dovadă constructivă a lemei locale generale lovász (engleză) // Journal of the ACM : journal. - 2010. - Vol. 57 , nr. 2 . — P. 1 . - doi : 10.1145/1667053.1667060 . - arXiv : 0903.0544 .
↑ Beck, József (1991), O abordare algoritmică a Lemei locale Lovász. I , Random Structures and Algorithms vol. 2 (4): 343–366 , DOI 10.1002/rsa.3240020402 .
↑ Fostul doctorand Robin Moser primește prestigiosul Premiu Gödel . ethz.ch . Preluat la 20 aprilie 2020. Arhivat din original la 31 octombrie 2021.
↑ ACM SIGACT - Premiul Gödel . sigact.org . Consultat la 20 aprilie 2020. Arhivat din original pe 9 ianuarie 2020. (nedefinit)
↑ Moser, Robin A. (2008), A constructive proof of the Lovász Local Leemma, arΧiv : 0810.4812 [cs.DS]. .
↑ Piotr Berman, Marek Karpinski și Alexander D. Scott, Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT ], ECCC TR 03-022(2003) Arhivat la 3 martie 2016 la Wayback Machine .