Русская Википедия:Алгоритмическая локальная лемма Ловаса
Алгоритмическая локальная лемма Ловаcа — лемма в теоретической информатике, позволяющая конструировать объекты, подчиняющиеся определённым ограничениям.
Из локальной леммы Ловаса следует, что вероятность того, что ни одно событие из некоторого множества «плохих» событий <math>\{A_1, \dots, A_n\}</math> не произойдёт, строго положительна, если эти события удовлетворяют некоторым дополнительным ограничениям. В то же время лемма неконструктивна и не позволяет явным образом конструировать примеры объектов, для которых эти события не наступают. В случае когда указанные события определяются конечным набором независимых друг от друга случайных величин, разработанный учёными Робином Мозером и Шаблон:Iw алгоритм типа «Лас-Вегас» с полиномиальным временем работы позволяет в явном виде вычислить некоторый набор значений этих величин, для которого не выполняется ни одно из рассматриваемых случайных событий[1].
Обзор локальной леммы Ловаса
Локальная лемма Ловаса является мощным инструментом, обычно используемым в вероятностном методе для доказательства существования некоторых сложных математических объектов с набором заданных признаков. Типичное доказательство сводится к рассмотрению свойств объекта с точки зрения теории вероятностей и использованию локальной леммы Ловаса для оценки вероятности отсутствия какого-либо из признаков. Отсутствие признака считается «плохим» событием, и если можно показать, что можно одновременно избежать всех таких «плохих» событий, то существование объекта доказано. Сама лемма формулируется следующим образом:
Алгоритмическая версия локальной леммы Ловаса
Локальная лемма Ловаса неконструктивна, поскольку она позволяет сделать вывод о существовании структурных свойств или сложных объектов, но не указывает, как можно их эффективно найти или построить на практике. При этом случайное семплирование из вероятностного пространства <math>\Omega</math>, вероятно, будет неэффективным, поскольку вероятность события, представляющего интерес,
- <math> \Pr \left( \overline{A_1} \wedge \cdots \wedge \overline{A_n} \right)</math>
ограничена только произведением малых величин
- <math> \prod_{A \in \mathcal{A}} (1-x(A)) </math> и поэтому, вероятно, будет очень мала.
В предположении, что все события из <math> \mathcal{A} </math> определяются конечным набором независимых друг от друга случайных величин <math> \mathcal{P} </math> из <math>\Omega</math>, Робин Мозер и Шаблон:Iw предложили эффективный случайный алгоритм, который находит набор случайных величин в <math> \mathcal{P} </math> таких, что все события из <math> \mathcal{A} </math> не выполняются.
Следовательно, этот алгоритм может использоваться для эффективного построения сложных объектов с предписанными характеристиками для большинства задач, к которым применима локальная лемма Ловаса.
История
Работе Мозера и Тардоса предшествовали и другие результаты, благодаря которым был достигнут прогресс в разработке алгоритмических версий локальной леммы Ловаса. В 1991 Шаблон:Iw впервые показал, что разработка алгоритмической версии леммы принципиально возможна[2]. В его работе формулировка леммы была более строгой, чем в первоначальном неконструктивном определении. Подход Бека требовал, чтобы для каждого <math>A \in \mathcal{A}</math> число зависимостей <math>A</math> было ограничено сверху как <math>|\Gamma(A)| < 2^{\frac{n}{48}}</math>. Неконструктивная версия локальной леммы допускает более слабое ограничение:
- <math>|\Gamma(A)| < \frac{2^{n}}{e}.</math>
Эта оценка является неулучшаемой. Последующие работы постепенно сдвигали эту оценку, пока Мозер и Тардос не предъявили алгоритм, который её достигает.
В 2020 году Шаблон:Iw и Шаблон:Iw получили премию Гёделя за алгоритмическую версию локальной леммы Ловаса[3][4].
Алгоритм
Пусть <math>v_P</math> — текущая реализация случайной величины <math> P \in \mathcal{P} </math>, а <math> (v_P)_{\mathcal{P}}</math> — реализация всех случайных величин из <math>\mathcal P</math>.
Уникальное минимальное подмножество случайных величин в <math> \mathcal{P} </math>, которые определяют, наступит ли событие <math> A </math>, обозначается <math> \text{vbl}(A) </math>.
Если событие <math> A </math> верно при вычислении <math> (v_P)_{\mathcal{P}}</math>, будем говорить, что вычисление <math> (v_P)_{\mathcal{P}}</math> удовлетворяет <math> A </math>, в противном случае оно избегает <math> A </math>.
Алгоритм работает следующим образом:
- Для каждой величины <math> P \in \mathcal{P} </math> случайным образом вычислить некоторую его реализацию <math> v_P </math>
- Пока существует <math> A \in \mathcal{A}</math> такое, что <math> (v_P)_{\mathcal{P}}</math> удовлетворяет <math> A </math>:
- Выбрать произвольное удовлетворенное событие <math> A \in \mathcal{A}</math>
- Для каждой величины <math> P \in \text{vbl}(A) </math> вычислить новую реализацию <math> v_P </math>
- Вернуть <math> (v_P)_{\mathcal{P}}</math>
На первом этапе алгоритм случайным образом инициализирует текущее назначение <math> v_P </math> для каждой случайной величины <math> P \in \mathcal{P}</math>. Это означает, что значение <math> v_P </math> выбирается случайным образом и независимо в соответствии с распределением случайной величины <math> P </math>. Затем алгоритм входит в основной цикл, который выполняется до тех пор, пока не будет найдена нужная реализация. На каждой итерации основного цикла алгоритм выбирает произвольное удовлетворенное событие <math> \mathcal{A} </math> и повторно выбирает все случайные величины, которые определяют <math> \mathcal{A} </math>.
Основная теорема
Пусть <math> \mathcal{P} </math> — конечное множество независимых в совокупности случайных величин в вероятностном пространстве <math>\Omega</math>, <math> \mathcal{A} </math> — конечное множество событий, определяемых этими величинами. Если существует набор <math> x : \mathcal{A} \to (0,1) </math> такой, что
- <math> \forall A \in \mathcal{A} : \Pr(A) \leq x(A) \prod_{B \in \Gamma(A)} (1-x(B)) </math>,
то существует реализация <math>\mathcal{P}</math>, избегающая всех событий из <math> \mathcal{A} </math>. Кроме того, описанный выше рандомизированный алгоритм повторно выбирает событие <math> A \in \mathcal{A} </math> не более чем
- <math> \frac{x(A)}{1-x(A)}</math>
раз, прежде чем он найдет требуемую реализацию. Таким образом, ожидаемое время выполнения алгоритма не превосходит
- <math> \sum_{A \in \mathcal{A}} \frac{x(A)}{1-x(A)}</math>[1].
Симметричная версия
Требования к <math> x </math> могут показаться сложными и неинтуитивными. Но его можно заменить тремя простыми условиями:
- <math> \forall A \in \mathcal{A}: |\Gamma(A)| \leq D </math>, то есть каждое событие <math> A </math> зависит не более чем от <math> D </math> других событий;
- <math> \forall A \in \mathcal{A}: \Pr(A) \leq p </math>, то есть вероятность каждого события <math> A </math> не превосходит <math> p
</math>;
- <math> e p (D+1) \leq 1 </math>, где <math> e </math> — это основание натурального логарифма.
Вариант локальной леммы Ловаса с этими тремя условиями вместо набора <math> x </math> называется симметричной локальной леммой Ловаса. Также можно сформулировать симметричную алгоритмическую локальную лемму Ловаса:
Пусть <math>\mathcal{P}</math> — конечный набор независимых в совокупности случайных величин и <math>\mathcal{A}</math> — конечный набор событий, определяемых этими величинами. Если вышеуказанные три условия выполняются, то существует реализация величин из <math>\mathcal{P}</math>, избегающая всех событий из <math>\mathcal{A} </math>. Кроме того, описанный выше рандомизированный алгоритм повторно выбирает событие <math> A \in \mathcal{A} </math> не больше чем <math>\frac{1}{D}</math> раз, прежде чем он найдет эту реализацию. Таким образом, общее ожидаемое время выполнения алгоритма не превосходит <math>\frac{n}{D}</math>.
Пример
В следующем примере показано, как алгоритмическая версия локальной леммы Ловаса может быть применена к простой задаче.
Пусть <math>\Phi</math> — конъюнктивная нормальная форма формулы над переменными <math>X_1, \dots, X_n</math>, содержащая <math>n</math> дизъюнктов и имеющая по крайней мере <math>k</math> литералов в каждом дизъюнкте, при этом каждая переменная <math>X_i</math> присутствует не более чем в <math>\frac{2^k}{ke} </math> дизъюнктах. Тогда <math>\Phi</math> выполнима.
Это утверждение можно доказать, используя симметричную версию алгоритмической локальной леммы Ловаса. Пусть <math>X_1, \dots, X_n</math> — множество независимых в совокупности случайных величин <math> \mathcal{P} </math>, которые выбираются равномерно и независимо друг от друга. Без ограничения общности можно считать, что в каждом дизъюнкте ровно <math>k</math> литералов. «Плохим» в данной задаче будет событие <math>A_i</math>, соответствующее тому, что <math>i</math>-й дизъюнкт не выполнен. Поскольку каждый дизъюнкт содержит <math>k</math> литералов (и, следовательно, <math>k</math> переменных) и все переменные выбираются случайным образом, можно оценить вероятность каждого «плохого» события следующим образом:
- <math>\Pr(A_i) = p = 2^{-k}.</math>
Поскольку каждая переменная может появляться не более чем в <math> \frac{2^k}{ke}</math> дизъюнктах, и в каждом дизъюнкте <math>k</math> переменных, каждое «плохое» событие <math>A_i</math> может зависеть не более чем от
- <math> D = k\left(\frac{2^k}{ke}-1\right) \leq \frac{2^k}{e} -1 </math>
других событий, следовательно
- <math>D+1 \leq \frac{2^k}{e}.</math>
Если умножить обе стороны на <math>ep</math>, получится
- <math> ep(D+1) \leq e 2^{-k} \frac{2^k}{e} = 1 </math>.
Из симметричной локальной леммы Ловаса следует, что вероятность реализации <math>X_1, \dots, X_n</math>, при которой все дизъюнкты из <math>\Phi</math> выполнены, не нулевая, и, следовательно, такая реализация должна существовать. Алгоритмическая лемма Ловаса позволяет найти такое присваивание за разумное время с помощью алгоритма, описанного выше. Алгоритм работает следующим образом:
Изначально берётся случайная реализация <math>X_1, \dots, X_n</math>. Пока вся формула <math>\Phi</math> не становится истинной, случайным образом выбирается невыполненный дизъюнкт <math>C</math> из <math>\Phi</math>, а затем всем переменным, которые встречаются в <math>C</math>, присваиваются новые значения, которые выбираются равномерно случайным образом. Как только все дизъюнкты из <math>\Phi</math> выполнены, алгоритм возвращает текущую реализацию. Следовательно, алгоритмическая локальная лемма Ловаса доказывает, что этот алгоритм будет работать не более чем за
- <math> \frac{n}{\frac{2^k}{e}-k} </math>
шагов на формулах, которые удовлетворяют двум вышеуказанным условиям. Более сильная версия приведенного выше утверждения доказана Мозером[5], см. также работу Бирмана, Карпинского и Скотта[6].
Параллельная версия
Описанный выше алгоритм хорошо подходит для распараллеливания, так как параллельная генерация новых реализаций для событий <math> A,B \in \mathcal{A}</math> таких, что <math> \text{vbl}(A) \cap \text{vbl}(B) = \emptyset </math>, эквивалентна последовательной. Следовательно, на каждой итерации основного цикла можно определить максимальный набор независимых удовлетворенных событий <math>S</math> и перегенерировать все события в <math>S</math> параллельно.
Если набор <math>x</math> удовлетворяет несколько более строгим условиям:
- <math> \forall A \in \mathcal{A} : \Pr(A) \leq (1 - \varepsilon) x(A) \prod_{B \in \Gamma(A)} (1-x(B)) </math>
для некоторого <math>\varepsilon > 0</math>, то параллельный алгоритм даёт ожидаемое время исполнения порядка
- <math> O\left(\frac{1}{\varepsilon} \log \sum_{A \in \mathcal{A}} \frac{x(A)}{1-x(A)}\right) </math>.
Примечания
- ↑ 1,0 1,1 Шаблон:Статья
- ↑ Шаблон:Citation.
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite arxiv.
- ↑ Piotr Berman, Marek Karpinski and Alexander D. Scott, Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT ], ECCC TR 03-022(2003) Шаблон:Wayback.
