Lovas algoritmiska lokala lemma

Lovas algoritmiska lokala lemma är ett lemma inom teoretisk datavetenskap som låter en konstruera objekt med vissa begränsningar.

Det följer av Lovas lokala lemma att sannolikheten att ingen av händelserna från någon uppsättning "dåliga" händelser kommer att inträffa är strikt positiv om dessa händelser uppfyller några ytterligare restriktioner. Samtidigt är lemmat inte konstruktivt och tillåter inte att man uttryckligen konstruerar exempel på objekt för vilka dessa händelser inte inträffar. I fallet när dessa händelser bestäms av en ändlig uppsättning slumpvariabler oberoende av varandra, låter algoritmen av Las Vegas -typen med polynom körtid utvecklad av forskarna Robin Moser och Gabor Tardos dig explicit beräkna en viss uppsättning av värden för dessa variabler, för vilka det inte finns någon av de betraktade slumpmässiga händelserna [1] . $\{A_{1},\dots ,A_{n}\}$

En översikt över Lovas lokala lemma

Lovas lokala lemma är ett kraftfullt verktyg som vanligtvis används i probabilistiska metoder för att bevisa förekomsten av några komplexa matematiska objekt med en uppsättning givna egenskaper. Ett typiskt bevis handlar om att överväga ett objekts egenskaper ur sannolikhetsteorin och att använda det lokala Lovas-lemmat för att uppskatta sannolikheten för frånvaron av någon av funktionerna. Frånvaron av ett tecken anses vara en "dålig" händelse, och om det kan visas att alla sådana "dåliga" händelser kan undvikas samtidigt, så bevisas föremålets existens. Själva lemmat är formulerat så här:

Låta vara en ändlig uppsättning händelser i sannolikhetsutrymmet . För varje , bestämmer let de hörn som gränsar till vertexet i beroendegrafen (i beroendegrafen är vertexen intill händelser som den inte är oberoende av). Om det finns en sådan mappning ${\mathcal {A}}=\{A_{1},\ldots ,A_{n}}\}$ $\Omega$ $A\in {\mathcal {A}}$ $\Gamma (A)$ $A$ $A$ $x:{\mathcal {A}}\to (0,1)$

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

då är sannolikheten att ingen av händelserna inträffar positiv, nämligen ${\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})).

En algoritmisk version av Lovas lokala lemma

Lovas lokala lemma är icke-konstruktivt eftersom det låter en sluta sig till existensen av strukturella egenskaper eller komplexa objekt, men anger inte hur man effektivt kan hitta eller konstruera dem i praktiken. I detta fall är slumpmässigt urval från sannolikhetsutrymmet sannolikt ineffektivt, eftersom sannolikheten för händelsen av intresse är $\Omega$

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

begränsas endast av produkten av små kvantiteter

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

och är därför sannolikt mycket liten.

Om vi antar att alla händelser från bestäms av en ändlig uppsättning av ömsesidigt oberoende slumpvariabler från , föreslog Robin Moser och Gabor Tardos en effektiv slumpmässig algoritm som hittar en uppsättning slumpvariabler så att alla händelser från inte håller. ${\mathcal {A}}$ ${\mathcal {P}}$ $\Omega$ ${\mathcal {P}}$ ${\mathcal {A}}$

Därför kan denna algoritm användas för att effektivt konstruera komplexa objekt med föreskrivna egenskaper för de flesta problem som det lokala Lovas-lemmat är tillämpligt på.

Historik

Mosers och Tardos arbete föregicks av andra resultat som ledde till framsteg i utvecklingen av algoritmiska versioner av Lovas lokala lemma. 1991 visade Joseph Beck för första gången att det i princip är möjligt att utveckla en algoritmisk version av lemma [2] . I hans arbete var formuleringen av lemma mer rigorös än i den ursprungliga icke-konstruktiva definitionen. Becks tillvägagångssätt krävde att för varje , antalet beroenden begränsas från ovan som . Den icke-konstruktiva versionen av det lokala lemma medger en svagare begränsning: $A\in {\mathcal {A}}$ $A$ $|\Gamma (A)|<2^{\frac {n}{48}}$

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

Denna uppskattning går inte att förbättra. Efterföljande arbete flyttade gradvis denna uppskattning tills Moser och Tardos presenterade en algoritm som uppnår den.

2020 fick Robin Moser och Gabor Tardos Gödelpriset för en algoritmisk version av Lovas lokala lemma [3] [4] .

Algoritm

Låt vara den nuvarande realiseringen av den slumpmässiga variabeln , och låt vara realiseringen av alla slumpvariabler från . $v_{P}$ $P\in {\mathcal {P))$ $(v_{P})_{\mathcal {P))$ ${\mathcal P}$

Den unika minsta delmängden av slumpvariabler som avgör om en händelse kommer att inträffa betecknas med . ${\mathcal {P}}$ $A$ ${\text{vbl}}(A)$

Om händelsen är sann under utvärdering , säger vi att utvärderingen uppfyller , annars undviker den . $A$ $(v_{P})_{\mathcal {P))$ $(v_{P})_{\mathcal {P))$ $A$ $A$

Algoritmen fungerar så här:

Beräkna slumpmässigt en del av dess implementering för varje värde $P\in {\mathcal {P))$ $v_{P}$
Så länge det finns en som uppfyller : $A\in {\mathcal {A}}$ $(v_{P})_{\mathcal {P))$ $A$
- Välj en godtycklig nöjd händelse $A\in {\mathcal {A}}$
- Beräkna en ny realisering för varje kvantitet $P\in {\text{vbl}}(A)$ $v_{P}$
Lämna tillbaka $(v_{P})_{\mathcal {P))$

I det första steget initierar algoritmen slumpmässigt den aktuella tilldelningen för varje slumpmässig variabel . Detta innebär att värdet väljs slumpmässigt och oberoende efter fördelningen av den slumpmässiga variabeln . Därefter går algoritmen in i huvudslingan, som exekveras tills den önskade implementeringen hittas. Vid varje iteration av huvudslingan väljer algoritmen en godtycklig nöjd händelse och väljer om alla slumpvariabler som bestämmer . $v_{P}$ $P\in {\mathcal {P))$ $v_{P}$ $P$ ${\mathcal {A}}$ ${\mathcal {A}}$

Huvudsats

Låta vara en ändlig uppsättning slumpmässiga variabler oberoende i helheten i sannolikheten utrymme , vara en ändlig uppsättning händelser som bestäms av dessa variabler. Om det finns ett set sådant ${\mathcal {P}}$ $\Omega$ ${\mathcal {A}}$ $x:{\mathcal {A}}\to (0,1)$

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

då finns det en implementering som undviker alla händelser från . Dessutom väljer den randomiserade algoritmen som beskrivs ovan en händelse som mest ${\mathcal {P}}$ ${\mathcal {A}}$ $A\in {\mathcal {A}}$

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

gånger innan den hittar den nödvändiga implementeringen. Således överstiger inte den förväntade exekveringstiden för algoritmen

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

[1] .

Symmetrisk version

Kraven kan verka komplexa och icke-intuitiva. Men det kan ersättas av tre enkla villkor: $x$

$\forall A\in {\mathcal {A):|\Gamma (A)|\leq D$ , det vill säga varje händelse beror inte på mer än andra händelser; $A$ $D$
$\forall A\in {\mathcal {A}}:\Pr(A)\leq p$ , det vill säga sannolikheten för varje händelse överstiger inte ; $A$ $p$
$ep(D+1)\leq 1$ , var är basen för den naturliga logaritmen för . $e$

En variant av det lokala Lovas-lemmat med dessa tre villkor istället för en mängd kallas det symmetriska lokala Lovas-lemmat. Det är också möjligt att formulera det symmetriska algoritmiska lokala Lovas-lemmat: $x$

Låt vara en ändlig uppsättning av ömsesidigt oberoende slumpvariabler och vara en ändlig uppsättning händelser som bestäms av dessa variabler. Om ovanstående tre villkor är uppfyllda, så finns det en realisering av värdena från som undviker alla händelser från . Dessutom väljer den randomiserade algoritmen som beskrivs ovan en händelse inte mer än en gång innan den hittar den implementeringen. Den totala förväntade exekveringstiden för algoritmen överstiger alltså inte . ${\mathcal {P}}$ $\mathcal{A}$ ${\mathcal {P}}$ ${\mathcal {A}}$ $A\in {\mathcal {A}}$ ${\frac {1}{D))$ ${\frac {n}{D}}$

Exempel

Följande exempel visar hur en algoritmisk version av Lovas lokala lemma kan appliceras på ett enkelt problem.

Låta vara en konjunktiv normal form av en formel över variabler som innehåller satser och har minst bokstaver i varje sats, och varje variabel finns i högst satser. Då genomförbart . $\Phi$ $X_{1},\dots ,X_{n}$ $n$ $k$ $X_{i}$ ${\frac {2^{k}}{ke}}$ $\Phi$

Detta påstående kan bevisas med hjälp av en symmetrisk version av Lovas algoritmiska lokala lemma. Låta vara en uppsättning av oberoende slumpvariabler , som väljs enhetligt och oberoende av varandra . Utan förlust av generalitet kan vi anta att det finns exakt bokstavliga ord i varje sats. Den "dåliga" händelsen i denna uppgift är den händelse som motsvarar det faktum att -th-satsen inte är uppfylld. Eftersom varje sats innehåller bokstaver (och därför variabler) och alla variabler väljs slumpmässigt, kan vi uppskatta sannolikheten för varje "dålig" händelse enligt följande: $X_{1},\dots ,X_{n}$ ${\mathcal {P}}$ $k$ $A_{i}$ $i$ $k$ $k$

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

Eftersom varje variabel kan förekomma i högst satser, och i varje sats av variabler, kan varje "dålig" händelse vara beroende av högst ${\frac {2^{k}}{ke}}$ $k$ $A_{i}$

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

andra evenemang, alltså

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

Om du multiplicerar båda sidor med får du $ep$

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

Det följer av det symmetriska lokala Lovas-lemmat att sannolikheten för en realisering under vilken alla satser av är uppfyllda inte är noll, och därför måste en sådan realisering existera. Lovas algoritmiska lemma gör att en sådan uppgift kan hittas i rimlig tid med den algoritm som beskrivs ovan. Algoritmen fungerar så här: $X_{1},\dots ,X_{n}$ $\Phi$

Inledningsvis tas en slumpmässig implementering . Tills hela formeln blir sann, väljs en otillfredsställd sats från slumpmässigt , och sedan tilldelas alla variabler som förekommer i nya värden, som väljs enhetligt slumpmässigt. När alla satser från är uppfyllda returnerar algoritmen den aktuella implementeringen. Därför bevisar Lovas algoritmiska lokala lemma att denna algoritm som mest kommer att köras in $X_{1},\dots ,X_{n}$ $\Phi$ $C$ $\Phi$ $C$ $\Phi$

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

steg på formler som uppfyller ovanstående två villkor. En starkare version av ovanstående påstående bevisades av Moser [5] , se även Birman, Karpinski och Scott [6] .

Parallell version

Algoritmen som beskrivs ovan är väl lämpad för parallellisering, eftersom den parallella genereringen av nya implementeringar för händelser så att , är ekvivalent med sekventiell generering. Därför är det vid varje iteration av huvudslingan möjligt att bestämma den maximala uppsättningen av oberoende tillfredsställda händelser och regenerera alla händelser parallellt. $A,B\in {\mathcal {A}}$ ${\text{vbl}}(A)\cap {\text{vbl}}(B)=\emptyset$ $S$ $S$

Om setet uppfyller lite strängare villkor: $x$

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

för vissa ger den parallella algoritmen den förväntade exekveringstiden för ordern $\varepsilon >0$

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

Anteckningar

↑ 1 2 Moser, Robin A.; Tardos, Gabor. Ett konstruktivt bevis på det allmänna lovász lokala lemmat (engelska) // Journal of the ACM : journal. - 2010. - Vol. 57 , nr. 2 . — S. 1 . - doi : 10.1145/1667053.1667060 . - arXiv : 0903.0544 .
↑ Beck, József (1991), An algorithmic approach to the Lovász Local Lemma. I , Random Structures and Algorithms vol 2 (4): 343–366 , DOI 10.1002/rsa.3240020402 .
↑ Tidigare doktoranden Robin Moser får prestigefyllda Gödelpriset . ethz.ch . Hämtad 20 april 2020. Arkiverad från originalet 31 oktober 2021.
↑ ACM SIGACT - Gödelpriset . sigact.org . Hämtad 20 april 2020. Arkiverad från originalet 9 januari 2020. (obestämd)
↑ Moser, Robin A. (2008), A constructive proof of the Lovász Local Lemma, arΧiv : 0810.4812 [cs.DS]. .
↑ Piotr Berman, Marek Karpinski och Alexander D. Scott, Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT ], ECCC TR 03-022(2003) Arkiverad 3 mars 2016 på Wayback Machine .