Алгоритмическая локальная лемма Ловаса
Алгоритмическая локальная лемма Ловаcа — лемма в теоретической информатике, позволяющая конструировать объекты, подчиняющиеся определённым ограничениям.
Из локальной леммы Ловаса следует, что вероятность того, что ни одно событие из некоторого множества «плохих» событий [math]\displaystyle{ \{A_1, \dots, A_n\} }[/math] не произойдёт, строго положительна, если эти события удовлетворяют некоторым дополнительным ограничениям. В то же время лемма неконструктивна и не позволяет явным образом конструировать примеры объектов, для которых эти события не наступают. В случае когда указанные события определяются конечным набором независимых друг от друга случайных величин, разработанный учёными Робином Мозером и Габором Тардосом[англ.] алгоритм типа «Лас-Вегас» с полиномиальным временем работы позволяет в явном виде вычислить некоторый набор значений этих величин, для которого не выполняется ни одно из рассматриваемых случайных событий[1].
Обзор локальной леммы Ловаса
Локальная лемма Ловаса является мощным инструментом, обычно используемым в вероятностном методе для доказательства существования некоторых сложных математических объектов с набором заданных признаков. Типичное доказательство сводится к рассмотрению свойств объекта с точки зрения теории вероятностей и использованию локальной леммы Ловаса для оценки вероятности отсутствия какого-либо из признаков. Отсутствие признака считается «плохим» событием, и если можно показать, что можно одновременно избежать всех таких «плохих» событий, то существование объекта доказано. Сама лемма формулируется следующим образом:
|
Алгоритмическая версия локальной леммы Ловаса
Локальная лемма Ловаса неконструктивна, поскольку она позволяет сделать вывод о существовании структурных свойств или сложных объектов, но не указывает, как можно их эффективно найти или построить на практике. При этом случайное семплирование из вероятностного пространства [math]\displaystyle{ \Omega }[/math], вероятно, будет неэффективным, поскольку вероятность события, представляющего интерес,
- [math]\displaystyle{ \Pr \left( \overline{A_1} \wedge \cdots \wedge \overline{A_n} \right) }[/math]
ограничена только произведением малых величин
- [math]\displaystyle{ \prod_{A \in \mathcal{A}} (1-x(A)) }[/math] и поэтому, вероятно, будет очень мала.
В предположении, что все события из [math]\displaystyle{ \mathcal{A} }[/math] определяются конечным набором независимых друг от друга случайных величин [math]\displaystyle{ \mathcal{P} }[/math] из [math]\displaystyle{ \Omega }[/math], Робин Мозер и Габор Тардос[англ.] предложили эффективный случайный алгоритм, который находит набор случайных величин в [math]\displaystyle{ \mathcal{P} }[/math] таких, что все события из [math]\displaystyle{ \mathcal{A} }[/math] не выполняются.
Следовательно, этот алгоритм может использоваться для эффективного построения сложных объектов с предписанными характеристиками для большинства задач, к которым применима локальная лемма Ловаса.
История
Работе Мозера и Тардоса предшествовали и другие результаты, благодаря которым был достигнут прогресс в разработке алгоритмических версий локальной леммы Ловаса. В 1991 Джозеф Бек[англ.] впервые показал, что разработка алгоритмической версии леммы принципиально возможна[2]. В его работе формулировка леммы была более строгой, чем в первоначальном неконструктивном определении. Подход Бека требовал, чтобы для каждого [math]\displaystyle{ A \in \mathcal{A} }[/math] число зависимостей [math]\displaystyle{ A }[/math] было ограничено сверху как [math]\displaystyle{ |\Gamma(A)| \lt 2^{\frac{n}{48}} }[/math]. Неконструктивная версия локальной леммы допускает более слабое ограничение:
- [math]\displaystyle{ |\Gamma(A)| \lt \frac{2^{n}}{e}. }[/math]
Эта оценка является неулучшаемой. Последующие работы постепенно сдвигали эту оценку, пока Мозер и Тардос не предъявили алгоритм, который её достигает.
В 2020 году Робин Мозер[англ.] и Габор Тардос[англ.] получили премию Гёделя за алгоритмическую версию локальной леммы Ловаса[3][4].
Алгоритм
Пусть [math]\displaystyle{ v_P }[/math] — текущая реализация случайной величины [math]\displaystyle{ P \in \mathcal{P} }[/math], а [math]\displaystyle{ (v_P)_{\mathcal{P}} }[/math] — реализация всех случайных величин из [math]\displaystyle{ \mathcal P }[/math].
Уникальное минимальное подмножество случайных величин в [math]\displaystyle{ \mathcal{P} }[/math], которые определяют, наступит ли событие [math]\displaystyle{ A }[/math], обозначается [math]\displaystyle{ \text{vbl}(A) }[/math].
Если событие [math]\displaystyle{ A }[/math] верно при вычислении [math]\displaystyle{ (v_P)_{\mathcal{P}} }[/math], будем говорить, что вычисление [math]\displaystyle{ (v_P)_{\mathcal{P}} }[/math] удовлетворяет [math]\displaystyle{ A }[/math], в противном случае оно избегает [math]\displaystyle{ A }[/math].
Алгоритм работает следующим образом:
- Для каждой величины [math]\displaystyle{ P \in \mathcal{P} }[/math] случайным образом вычислить некоторую его реализацию [math]\displaystyle{ v_P }[/math]
- Пока существует [math]\displaystyle{ A \in \mathcal{A} }[/math] такое, что [math]\displaystyle{ (v_P)_{\mathcal{P}} }[/math] удовлетворяет [math]\displaystyle{ A }[/math]:
- Выбрать произвольное удовлетворенное событие [math]\displaystyle{ A \in \mathcal{A} }[/math]
- Для каждой величины [math]\displaystyle{ P \in \text{vbl}(A) }[/math] вычислить новую реализацию [math]\displaystyle{ v_P }[/math]
- Вернуть [math]\displaystyle{ (v_P)_{\mathcal{P}} }[/math]
На первом этапе алгоритм случайным образом инициализирует текущее назначение [math]\displaystyle{ v_P }[/math] для каждой случайной величины [math]\displaystyle{ P \in \mathcal{P} }[/math]. Это означает, что значение [math]\displaystyle{ v_P }[/math] выбирается случайным образом и независимо в соответствии с распределением случайной величины [math]\displaystyle{ P }[/math]. Затем алгоритм входит в основной цикл, который выполняется до тех пор, пока не будет найдена нужная реализация. На каждой итерации основного цикла алгоритм выбирает произвольное удовлетворенное событие [math]\displaystyle{ \mathcal{A} }[/math] и повторно выбирает все случайные величины, которые определяют [math]\displaystyle{ \mathcal{A} }[/math].
Основная теорема
Пусть [math]\displaystyle{ \mathcal{P} }[/math] — конечное множество независимых в совокупности случайных величин в вероятностном пространстве [math]\displaystyle{ \Omega }[/math], [math]\displaystyle{ \mathcal{A} }[/math] — конечное множество событий, определяемых этими величинами. Если существует набор [math]\displaystyle{ x : \mathcal{A} \to (0,1) }[/math] такой, что
- [math]\displaystyle{ \forall A \in \mathcal{A} : \Pr(A) \leq x(A) \prod_{B \in \Gamma(A)} (1-x(B)) }[/math],
то существует реализация [math]\displaystyle{ \mathcal{P} }[/math], избегающая всех событий из [math]\displaystyle{ \mathcal{A} }[/math]. Кроме того, описанный выше рандомизированный алгоритм повторно выбирает событие [math]\displaystyle{ A \in \mathcal{A} }[/math] не более чем
- [math]\displaystyle{ \frac{x(A)}{1-x(A)} }[/math]
раз, прежде чем он найдет требуемую реализацию. Таким образом, ожидаемое время выполнения алгоритма не превосходит
- [math]\displaystyle{ \sum_{A \in \mathcal{A}} \frac{x(A)}{1-x(A)} }[/math][1].
Симметричная версия
Требования к [math]\displaystyle{ x }[/math] могут показаться сложными и неинтуитивными. Но его можно заменить тремя простыми условиями:
- [math]\displaystyle{ \forall A \in \mathcal{A}: |\Gamma(A)| \leq D }[/math], то есть каждое событие [math]\displaystyle{ A }[/math] зависит не более чем от [math]\displaystyle{ D }[/math] других событий;
- [math]\displaystyle{ \forall A \in \mathcal{A}: \Pr(A) \leq p }[/math], то есть вероятность каждого события [math]\displaystyle{ A }[/math] не превосходит [math]\displaystyle{ p }[/math];
- [math]\displaystyle{ e p (D+1) \leq 1 }[/math], где [math]\displaystyle{ e }[/math] — это основание натурального логарифма.
Вариант локальной леммы Ловаса с этими тремя условиями вместо набора [math]\displaystyle{ x }[/math] называется симметричной локальной леммой Ловаса. Также можно сформулировать симметричную алгоритмическую локальную лемму Ловаса:
Пусть [math]\displaystyle{ \mathcal{P} }[/math] — конечный набор независимых в совокупности случайных величин и [math]\displaystyle{ \mathcal{A} }[/math] — конечный набор событий, определяемых этими величинами. Если вышеуказанные три условия выполняются, то существует реализация величин из [math]\displaystyle{ \mathcal{P} }[/math], избегающая всех событий из [math]\displaystyle{ \mathcal{A} }[/math]. Кроме того, описанный выше рандомизированный алгоритм повторно выбирает событие [math]\displaystyle{ A \in \mathcal{A} }[/math] не больше чем [math]\displaystyle{ \frac{1}{D} }[/math] раз, прежде чем он найдет эту реализацию. Таким образом, общее ожидаемое время выполнения алгоритма не превосходит [math]\displaystyle{ \frac{n}{D} }[/math].
Пример
В следующем примере показано, как алгоритмическая версия локальной леммы Ловаса может быть применена к простой задаче.
Пусть [math]\displaystyle{ \Phi }[/math] — конъюнктивная нормальная форма формулы над переменными [math]\displaystyle{ X_1, \dots, X_n }[/math], содержащая [math]\displaystyle{ n }[/math] дизъюнктов и имеющая по крайней мере [math]\displaystyle{ k }[/math] литералов в каждом дизъюнкте, при этом каждая переменная [math]\displaystyle{ X_i }[/math] присутствует не более чем в [math]\displaystyle{ \frac{2^k}{ke} }[/math] дизъюнктах. Тогда [math]\displaystyle{ \Phi }[/math] выполнима.
Это утверждение можно доказать, используя симметричную версию алгоритмической локальной леммы Ловаса. Пусть [math]\displaystyle{ X_1, \dots, X_n }[/math] — множество независимых в совокупности случайных величин [math]\displaystyle{ \mathcal{P} }[/math], которые выбираются равномерно и независимо друг от друга. Без ограничения общности можно считать, что в каждом дизъюнкте ровно [math]\displaystyle{ k }[/math] литералов. «Плохим» в данной задаче будет событие [math]\displaystyle{ A_i }[/math], соответствующее тому, что [math]\displaystyle{ i }[/math]-й дизъюнкт не выполнен. Поскольку каждый дизъюнкт содержит [math]\displaystyle{ k }[/math] литералов (и, следовательно, [math]\displaystyle{ k }[/math] переменных) и все переменные выбираются случайным образом, можно оценить вероятность каждого «плохого» события следующим образом:
- [math]\displaystyle{ \Pr(A_i) = p = 2^{-k}. }[/math]
Поскольку каждая переменная может появляться не более чем в [math]\displaystyle{ \frac{2^k}{ke} }[/math] дизъюнктах, и в каждом дизъюнкте [math]\displaystyle{ k }[/math] переменных, каждое «плохое» событие [math]\displaystyle{ A_i }[/math] может зависеть не более чем от
- [math]\displaystyle{ D = k\left(\frac{2^k}{ke}-1\right) \leq \frac{2^k}{e} -1 }[/math]
других событий, следовательно
- [math]\displaystyle{ D+1 \leq \frac{2^k}{e}. }[/math]
Если умножить обе стороны на [math]\displaystyle{ ep }[/math], получится
- [math]\displaystyle{ ep(D+1) \leq e 2^{-k} \frac{2^k}{e} = 1 }[/math].
Из симметричной локальной леммы Ловаса следует, что вероятность реализации [math]\displaystyle{ X_1, \dots, X_n }[/math], при которой все дизъюнкты из [math]\displaystyle{ \Phi }[/math] выполнены, не нулевая, и, следовательно, такая реализация должна существовать. Алгоритмическая лемма Ловаса позволяет найти такое присваивание за разумное время с помощью алгоритма, описанного выше. Алгоритм работает следующим образом:
Изначально берётся случайная реализация [math]\displaystyle{ X_1, \dots, X_n }[/math]. Пока вся формула [math]\displaystyle{ \Phi }[/math] не становится истинной, случайным образом выбирается невыполненный дизъюнкт [math]\displaystyle{ C }[/math] из [math]\displaystyle{ \Phi }[/math], а затем всем переменным, которые встречаются в [math]\displaystyle{ C }[/math], присваиваются новые значения, которые выбираются равномерно случайным образом. Как только все дизъюнкты из [math]\displaystyle{ \Phi }[/math] выполнены, алгоритм возвращает текущую реализацию. Следовательно, алгоритмическая локальная лемма Ловаса доказывает, что этот алгоритм будет работать не более чем за
- [math]\displaystyle{ \frac{n}{\frac{2^k}{e}-k} }[/math]
шагов на формулах, которые удовлетворяют двум вышеуказанным условиям. Более сильная версия приведенного выше утверждения доказана Мозером[5], см. также работу Бирмана, Карпинского и Скотта[6].
Параллельная версия
Описанный выше алгоритм хорошо подходит для распараллеливания, так как параллельная генерация новых реализаций для событий [math]\displaystyle{ A,B \in \mathcal{A} }[/math] таких, что [math]\displaystyle{ \text{vbl}(A) \cap \text{vbl}(B) = \emptyset }[/math], эквивалентна последовательной. Следовательно, на каждой итерации основного цикла можно определить максимальный набор независимых удовлетворенных событий [math]\displaystyle{ S }[/math] и перегенерировать все события в [math]\displaystyle{ S }[/math] параллельно.
Если набор [math]\displaystyle{ x }[/math] удовлетворяет несколько более строгим условиям:
- [math]\displaystyle{ \forall A \in \mathcal{A} : \Pr(A) \leq (1 - \varepsilon) x(A) \prod_{B \in \Gamma(A)} (1-x(B)) }[/math]
для некоторого [math]\displaystyle{ \varepsilon \gt 0 }[/math], то параллельный алгоритм даёт ожидаемое время исполнения порядка
- [math]\displaystyle{ O\left(\frac{1}{\varepsilon} \log \sum_{A \in \mathcal{A}} \frac{x(A)}{1-x(A)}\right) }[/math].
Примечания
- ↑ 1,0 1,1 Moser, Robin A.; Tardos, Gábor. A constructive proof of the general lovász local lemma (англ.) // Journal of the ACM : journal. — 2010. — Vol. 57, no. 2. — P. 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 Т. 2 (4): 343–366, DOI 10.1002/rsa.3240020402.
- ↑ Former doctoral student Robin Moser receives prestigious Gödel Prize (англ.). ethz.ch. Дата обращения: 20 апреля 2020. Архивировано 31 октября 2021 года.
- ↑ ACM SIGACT - Gödel Prize . sigact.org. Дата обращения: 20 апреля 2020. Архивировано 9 января 2020 года.
- ↑ Moser, Robin A. (2008), A constructive proof of the Lovász Local Lemma, arΧiv:0810.4812 [cs.DS]..
- ↑ Piotr Berman, Marek Karpinski and Alexander D. Scott, Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT ], ECCC TR 03-022(2003) Архивная копия от 3 марта 2016 на Wayback Machine.