Главная
Алгоритмическая локальная лемма Ловаcа — лемма в теоретической информатике, позволяющая конструировать объекты, подчиняющиеся определённым ограничениям.
Из локальной леммы Ловаса следует, что вероятность того, что ни одно событие из некоторого множества «плохих» событий { A 1 , … , A n } {displaystyle {A_{1},dots ,A_{n}}} не произойдёт, строго положительна, если эти события удовлетворяют некоторым дополнительным ограничениям. В то же время лемма неконструктивна и не позволяет явным образом конструировать примеры объектов, для которых эти события не наступают. В случае когда указанные события определяются конечным набором независимых друг от друга случайных величин, разработанный учёными Робином Мозером и Габором Тардосом алгоритм типа «Лас-Вегас» с полиномиальным временем работы позволяет в явном виде вычислить некоторый набор значений этих величин, для которого не выполняется ни одно из рассматриваемых случайных событий.
Обзор локальной леммы Ловаса
Локальная лемма Ловаса является мощным инструментом, обычно используемым в вероятностном методе для доказательства существования некоторых сложных математических объектов с набором заданных признаков. Типичное доказательство сводится к рассмотрению свойств объекта с точки зрения теории вероятностей и использованию локальной леммы Ловаса для оценки вероятности отсутствия какого-либо из признаков. Отсутствие признака считается «плохим» событием, и если можно показать, что можно одновременно избежать всех таких «плохих» событий, то существование объекта доказано. Сама лемма формулируется следующим образом:
Алгоритмическая версия локальной леммы Ловаса
Локальная лемма Ловаса неконструктивна, поскольку она позволяет сделать вывод о существовании структурных свойств или сложных объектов, но не указывает, как можно их эффективно найти или построить на практике. При этом случайное семплирование из вероятностного пространства Ω {displaystyle Omega } , вероятно, будет неэффективным, поскольку вероятность события, представляющего интерес,
Pr ( A 1 ¯ ∧ ⋯ ∧ A n ¯ ) {displaystyle Pr left({overline {A_{1}}}wedge cdots wedge {overline {A_{n}}} ight)}ограничена только произведением малых величин
∏ A ∈ A ( 1 − x ( A ) ) {displaystyle prod _{Ain {mathcal {A}}}(1-x(A))} и поэтому, вероятно, будет очень мала.В предположении, что все события из A {displaystyle {mathcal {A}}} определяются конечным набором независимых друг от друга случайных величин P {displaystyle {mathcal {P}}} из Ω {displaystyle Omega } , Робин Мозер и Габор Тардос предложили эффективный случайный алгоритм, который находит набор случайных величин в P {displaystyle {mathcal {P}}} таких, что все события из A {displaystyle {mathcal {A}}} не выполняются.
Следовательно, этот алгоритм может использоваться для эффективного построения сложных объектов с предписанными характеристиками для большинства задач, к которым применима локальная лемма Ловаса.
История
Работе Мозера и Тардоса предшествовали и другие результаты, благодаря которым был достигнут прогресс в разработке алгоритмических версий локальной леммы Ловаса. В 1991 Джозеф Бек впервые показал, что разработка алгоритмической версии леммы принципиально возможна. В его работе формулировка леммы была более строгой, чем в первоначальном неконструктивном определении. Подход Бека требовал, чтобы для каждого A ∈ A {displaystyle Ain {mathcal {A}}} число зависимостей A {displaystyle A} было ограничено сверху как | Γ ( A ) | < 2 n 48 {displaystyle |Gamma (A)|<2^{frac {n}{48}}} . Неконструктивная версия локальной леммы допускает более слабое ограничение:
| Γ ( A ) | < 2 n e . {displaystyle |Gamma (A)|<{frac {2^{n}}{e}}.}Эта оценка является неулучшаемой. Последующие работы постепенно сдвигали эту оценку, пока Мозер и Тардос не предъявили алгоритм, который её достигает.
В 2020 году Робин Мозер и Габор Тардос получили премию Гёделя за алгоритмическую версию локальной леммы Ловаса.
Алгоритм
Пусть v P {displaystyle v_{P}} — текущая реализация случайной величины P ∈ P {displaystyle Pin {mathcal {P}}} , а ( v P ) P {displaystyle (v_{P})_{mathcal {P}}} — реализация всех случайных величин из P {displaystyle {mathcal {P}}} .
Уникальное минимальное подмножество случайных величин в P {displaystyle {mathcal {P}}} , которые определяют, наступит ли событие A {displaystyle A} , обозначается vbl ( A ) {displaystyle { ext{vbl}}(A)} .
Если событие A {displaystyle A} верно при вычислении ( v P ) P {displaystyle (v_{P})_{mathcal {P}}} , будем говорить, что вычисление ( v P ) P {displaystyle (v_{P})_{mathcal {P}}} удовлетворяет A {displaystyle A} , в противном случае оно избегает A {displaystyle A} .
Алгоритм работает следующим образом:
- Выбрать произвольное удовлетворенное событие A ∈ A {displaystyle Ain {mathcal {A}}}
- Для каждой величины P ∈ vbl ( A ) {displaystyle Pin { ext{vbl}}(A)} вычислить новую реализацию v P {displaystyle v_{P}}
На первом этапе алгоритм случайным образом инициализирует текущее назначение v P {displaystyle v_{P}} для каждой случайной величины P ∈ P {displaystyle Pin {mathcal {P}}} . Это означает, что значение v P {displaystyle v_{P}} выбирается случайным образом и независимо в соответствии с распределением случайной величины P {displaystyle P} . Затем алгоритм входит в основной цикл, который выполняется до тех пор, пока не будет найдена нужная реализация. На каждой итерации основного цикла алгоритм выбирает произвольное удовлетворенное событие A {displaystyle {mathcal {A}}} и повторно выбирает все случайные величины, которые определяют A {displaystyle {mathcal {A}}} .
Основная теорема
Пусть P {displaystyle {mathcal {P}}} — конечное множество независимых в совокупности случайных величин в вероятностном пространстве Ω {displaystyle Omega } , A {displaystyle {mathcal {A}}} — конечное множество событий, определяемых этими величинами. Если существует набор x : A → ( 0 , 1 ) {displaystyle x:{mathcal {A}} o (0,1)} такой, что
∀ A ∈ A : Pr ( A ) ≤ x ( A ) ∏ B ∈ Γ ( A ) ( 1 − x ( B ) ) {displaystyle forall Ain {mathcal {A}}:Pr(A)leq x(A)prod _{Bin Gamma (A)}(1-x(B))} ,то существует реализация P {displaystyle {mathcal {P}}} , избегающая всех событий из A {displaystyle {mathcal {A}}} . Кроме того, описанный выше рандомизированный алгоритм повторно выбирает событие A ∈ A {displaystyle Ain {mathcal {A}}} не более чем
x ( A ) 1 − x ( A ) {displaystyle {frac {x(A)}{1-x(A)}}}раз, прежде чем он найдет требуемую реализацию. Таким образом, ожидаемое время выполнения алгоритма не превосходит
∑ A ∈ A x ( A ) 1 − x ( A ) {displaystyle sum _{Ain {mathcal {A}}}{frac {x(A)}{1-x(A)}}} .Симметричная версия
Требования к x {displaystyle x} могут показаться сложными и неинтуитивными. Но его можно заменить тремя простыми условиями:
- ∀ A ∈ A : | Γ ( A ) | ≤ D {displaystyle forall Ain {mathcal {A}}:|Gamma (A)|leq D} , то есть каждое событие A {displaystyle A} зависит не более чем от D {displaystyle D} других событий;
- ∀ A ∈ A : Pr ( A ) ≤ p {displaystyle forall Ain {mathcal {A}}:Pr(A)leq p} , то есть вероятность каждого события A {displaystyle A} не превосходит p {displaystyle p} ;
- e p ( D + 1 ) ≤ 1 {displaystyle ep(D+1)leq 1} , где e {displaystyle e} — это основание натурального логарифма.
Вариант локальной леммы Ловаса с этими тремя условиями вместо набора x {displaystyle x} называется симметричной локальной леммой Ловаса. Также можно сформулировать симметричную алгоритмическую локальную лемму Ловаса:
Пусть P {displaystyle {mathcal {P}}} — конечный набор независимых в совокупности случайных величин и A {displaystyle {mathcal {A}}} — конечный набор событий, определяемых этими величинами. Если вышеуказанные три условия выполняются, то существует реализация величин из P {displaystyle {mathcal {P}}} , избегающая всех событий из A {displaystyle {mathcal {A}}} . Кроме того, описанный выше рандомизированный алгоритм повторно выбирает событие A ∈ A {displaystyle Ain {mathcal {A}}} не больше чем 1 D {displaystyle {frac {1}{D}}} раз, прежде чем он найдет эту реализацию. Таким образом, общее ожидаемое время выполнения алгоритма не превосходит n D {displaystyle {frac {n}{D}}} .
Пример
В следующем примере показано, как алгоритмическая версия локальной леммы Ловаса может быть применена к простой задаче.
Пусть Φ {displaystyle Phi } — конъюнктивная нормальная форма формулы над переменными X 1 , … , X n {displaystyle X_{1},dots ,X_{n}} , содержащая n {displaystyle n} дизъюнктов и имеющая по крайней мере k {displaystyle k} литералов в каждом дизъюнкте, при этом каждая переменная X i {displaystyle X_{i}} присутствует не более чем в 2 k k e {displaystyle {frac {2^{k}}{ke}}} дизъюнктах. Тогда Φ {displaystyle Phi } выполнима.
Это утверждение можно доказать, используя симметричную версию алгоритмической локальной леммы Ловаса. Пусть X 1 , … , X n {displaystyle X_{1},dots ,X_{n}} — множество независимых в совокупности случайных величин P {displaystyle {mathcal {P}}} , которые выбираются равномерно и независимо друг от друга. Без ограничения общности можно считать, что в каждом дизъюнкте ровно k {displaystyle k} литералов. «Плохим» в данной задаче будет событие A i {displaystyle A_{i}} , соответствующее тому, что i {displaystyle i} -й дизъюнкт не выполнен. Поскольку каждый дизъюнкт содержит k {displaystyle k} литералов (и, следовательно, k {displaystyle k} переменных) и все переменные выбираются случайным образом, можно оценить вероятность каждого «плохого» события следующим образом:
Pr ( A i ) = p = 2 − k . {displaystyle Pr(A_{i})=p=2^{-k}.}Поскольку каждая переменная может появляться не более чем в 2 k k e {displaystyle {frac {2^{k}}{ke}}} дизъюнктах, и в каждом дизъюнкте k {displaystyle k} переменных, каждое «плохое» событие A i {displaystyle A_{i}} может зависеть не более чем от
D = k ( 2 k k e − 1 ) ≤ 2 k e − 1 {displaystyle D=kleft({frac {2^{k}}{ke}}-1 ight)leq {frac {2^{k}}{e}}-1}других событий, следовательно
D + 1 ≤ 2 k e . {displaystyle D+1leq {frac {2^{k}}{e}}.}Если умножить обе стороны на e p {displaystyle ep} , получится
e p ( D + 1 ) ≤ e 2 − k 2 k e = 1 {displaystyle ep(D+1)leq e2^{-k}{frac {2^{k}}{e}}=1} .Из симметричной локальной леммы Ловаса следует, что вероятность реализации X 1 , … , X n {displaystyle X_{1},dots ,X_{n}} , при которой все дизъюнкты из Φ {displaystyle Phi } выполнены, не нулевая, и, следовательно, такая реализация должна существовать. Алгоритмическая лемма Ловаса позволяет найти такое присваивание за разумное время с помощью алгоритма, описанного выше. Алгоритм работает следующим образом:
Изначально берётся случайная реализация X 1 , … , X n {displaystyle X_{1},dots ,X_{n}} . Пока вся формула Φ {displaystyle Phi } не становится истинной, случайным образом выбирается невыполненный дизъюнкт C {displaystyle C} из Φ {displaystyle Phi } , а затем всем переменным, которые встречаются в C {displaystyle C} , присваиваются новые значения, которые выбираются равномерно случайным образом. Как только все дизъюнкты из Φ {displaystyle Phi } выполнены, алгоритм возвращает текущую реализацию. Следовательно, алгоритмическая локальная лемма Ловаса доказывает, что этот алгоритм будет работать не более чем за
n 2 k e − k {displaystyle {frac {n}{{frac {2^{k}}{e}}-k}}}шагов на формулах, которые удовлетворяют двум вышеуказанным условиям. Более сильная версия приведенного выше утверждения доказана Мозером, см. также работу Бирмана, Карпинского и Скотта.
Параллельная версия
Описанный выше алгоритм хорошо подходит для распараллеливания, так как параллельная генерация новых реализаций для событий A , B ∈ A {displaystyle A,Bin {mathcal {A}}} таких, что vbl ( A ) ∩ vbl ( B ) = ∅ {displaystyle { ext{vbl}}(A)cap { ext{vbl}}(B)=emptyset } , эквивалентна последовательной. Следовательно, на каждой итерации основного цикла можно определить максимальный набор независимых удовлетворенных событий S {displaystyle S} и перегенерировать все события в S {displaystyle S} параллельно.
Если набор x {displaystyle x} удовлетворяет несколько более строгим условиям:
∀ A ∈ A : Pr ( A ) ≤ ( 1 − ε ) x ( A ) ∏ B ∈ Γ ( A ) ( 1 − x ( B ) ) {displaystyle forall Ain {mathcal {A}}:Pr(A)leq (1-varepsilon )x(A)prod _{Bin Gamma (A)}(1-x(B))}для некоторого ε > 0 {displaystyle varepsilon >0} , то параллельный алгоритм даёт ожидаемое время исполнения порядка
O ( 1 ε log ∑ A ∈ A x ( A ) 1 − x ( A ) ) {displaystyle Oleft({frac {1}{varepsilon }}log sum _{Ain {mathcal {A}}}{frac {x(A)}{1-x(A)}} ight)} .