Алгоритмическая локальная лемма Ловаса

Алгоритмическая локальная лемма Ловаcа — лемма в теоретической информатике, позволяющая конструировать объекты, подчиняющиеся определённым ограничениям.

Из локальной леммы Ловаса следует, что вероятность того, что ни одно событие из некоторого множества «плохих» событий $\{A_{1},\dots ,A_{n}\}$ не произойдёт, строго положительна, если эти события удовлетворяют некоторым дополнительным ограничениям. В то же время лемма неконструктивна и не позволяет явным образом конструировать примеры объектов, для которых эти события не наступают. В случае когда указанные события определяются конечным набором независимых друг от друга случайных величин, разработанный учёными Робином Мозером и Габором Тардосом алгоритм типа «Лас-Вегас» с полиномиальным временем работы позволяет в явном виде вычислить некоторый набор значений этих величин, для которого не выполняется ни одно из рассматриваемых случайных событий[1].

Обзор локальной леммы Ловаса

Локальная лемма Ловаса является мощным инструментом, обычно используемым в вероятностном методе для доказательства существования некоторых сложных математических объектов с набором заданных признаков. Типичное доказательство сводится к рассмотрению свойств объекта с точки зрения теории вероятностей и использованию локальной леммы Ловаса для оценки вероятности отсутствия какого-либо из признаков. Отсутствие признака считается «плохим» событием, и если можно показать, что можно одновременно избежать всех таких «плохих» событий, то существование объекта доказано. Сама лемма формулируется следующим образом:

Пусть ${\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)),$

то вероятность того, что ни одно из событий ${\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})).$

Алгоритмическая версия локальной леммы Ловаса

Локальная лемма Ловаса неконструктивна, поскольку она позволяет сделать вывод о существовании структурных свойств или сложных объектов, но не указывает, как можно их эффективно найти или построить на практике. При этом случайное семплирование из вероятностного пространства $\Omega$ , вероятно, будет неэффективным, поскольку вероятность события, представляющего интерес,

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

ограничена только произведением малых величин

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

и поэтому, вероятно, будет очень мала.

В предположении, что все события из ${\mathcal {A}}$ определяются конечным набором независимых друг от друга случайных величин ${\mathcal {P}}$ из $\Omega$ , Робин Мозер и Габор Тардос предложили эффективный случайный алгоритм, который находит набор случайных величин в ${\mathcal {P}}$ таких, что все события из ${\mathcal {A}}$ не выполняются.

Следовательно, этот алгоритм может использоваться для эффективного построения сложных объектов с предписанными характеристиками для большинства задач, к которым применима локальная лемма Ловаса.

История

Работе Мозера и Тардоса предшествовали и другие результаты, благодаря которым был достигнут прогресс в разработке алгоритмических версий локальной леммы Ловаса. В 1991 Джозеф Бек впервые показал, что разработка алгоритмической версии леммы принципиально возможна[2]. В его работе формулировка леммы была более строгой, чем в первоначальном неконструктивном определении. Подход Бека требовал, чтобы для каждого $A\in {\mathcal {A}}$ число зависимостей $A$ было ограничено сверху как $|\Gamma (A)|<2^{\frac {n}{48}}$ . Неконструктивная версия локальной леммы допускает более слабое ограничение:

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

Эта оценка является неулучшаемой. Последующие работы постепенно сдвигали эту оценку, пока Мозер и Тардос не предъявили алгоритм, который её достигает.

В 2020 году Робин Мозер и Габор Тардос получили премию Гёделя за алгоритмическую версию локальной леммы Ловаса[3][4].

Алгоритм

Пусть $v_{P}$ — текущая реализация случайной величины $P\in {\mathcal {P}}$ , а $(v_{P})_{\mathcal {P}}$ — реализация всех случайных величин из ${\mathcal {P}}$ .

Уникальное минимальное подмножество случайных величин в ${\mathcal {P}}$ , которые определяют, наступит ли событие $A$ , обозначается ${\text{vbl}}(A)$ .

Если событие $A$ верно при вычислении $(v_{P})_{\mathcal {P}}$ , будем говорить, что вычисление $(v_{P})_{\mathcal {P}}$ удовлетворяет $A$ , в противном случае оно избегает $A$ .

Алгоритм работает следующим образом:

Для каждой величины $P\in {\mathcal {P}}$ случайным образом вычислить некоторую его реализацию $v_{P}$
Пока существует $A\in {\mathcal {A}}$ $\text{[math]}$ такое, что $(v_{P})_{\mathcal {P}}$ $\text{[math]}$ удовлетворяет $A$ $\text{[math]}$ :
- Выбрать произвольное удовлетворенное событие $A\in {\mathcal {A}}$
- Для каждой величины $P\in {\text{vbl}}(A)$ вычислить новую реализацию $v_{P}$
Вернуть $(v_{P})_{\mathcal {P}}$

На первом этапе алгоритм случайным образом инициализирует текущее назначение $v_{P}$ для каждой случайной величины $P\in {\mathcal {P}}$ . Это означает, что значение $v_{P}$ выбирается случайным образом и независимо в соответствии с распределением случайной величины $P$ . Затем алгоритм входит в основной цикл, который выполняется до тех пор, пока не будет найдена нужная реализация. На каждой итерации основного цикла алгоритм выбирает произвольное удовлетворенное событие ${\mathcal {A}}$ и повторно выбирает все случайные величины, которые определяют ${\mathcal {A}}$ .

Основная теорема

Пусть ${\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))

,

то существует реализация ${\mathcal {P}}$ , избегающая всех событий из ${\mathcal {A}}$ . Кроме того, описанный выше рандомизированный алгоритм повторно выбирает событие $A\in {\mathcal {A}}$ не более чем

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

раз, прежде чем он найдет требуемую реализацию. Таким образом, ожидаемое время выполнения алгоритма не превосходит

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

[1].

Симметричная версия

Требования к $x$ могут показаться сложными и неинтуитивными. Но его можно заменить тремя простыми условиями:

$\forall A\in {\mathcal {A}}:|\Gamma (A)|\leq D$ , то есть каждое событие $A$ зависит не более чем от $D$ других событий;
$\forall A\in {\mathcal {A}}:\Pr(A)\leq p$ , то есть вероятность каждого события $A$ не превосходит $p$ ;
$ep(D+1)\leq 1$ , где $e$ — это основание натурального логарифма.

Вариант локальной леммы Ловаса с этими тремя условиями вместо набора $x$ называется симметричной локальной леммой Ловаса. Также можно сформулировать симметричную алгоритмическую локальную лемму Ловаса:

Пусть ${\mathcal {P}}$ — конечный набор независимых в совокупности случайных величин и ${\mathcal {A}}$ — конечный набор событий, определяемых этими величинами. Если вышеуказанные три условия выполняются, то существует реализация величин из ${\mathcal {P}}$ , избегающая всех событий из ${\mathcal {A}}$ . Кроме того, описанный выше рандомизированный алгоритм повторно выбирает событие $A\in {\mathcal {A}}$ не больше чем ${\frac {1}{D}}$ раз, прежде чем он найдет эту реализацию. Таким образом, общее ожидаемое время выполнения алгоритма не превосходит ${\frac {n}{D}}$ .

Пример

В следующем примере показано, как алгоритмическая версия локальной леммы Ловаса может быть применена к простой задаче.

Пусть $\Phi$ — конъюнктивная нормальная форма формулы над переменными $X_{1},\dots ,X_{n}$ , содержащая $n$ дизъюнктов и имеющая по крайней мере $k$ литералов в каждом дизъюнкте, при этом каждая переменная $X_{i}$ присутствует не более чем в ${\frac {2^{k}}{ke}}$ дизъюнктах. Тогда $\Phi$ выполнима.

Это утверждение можно доказать, используя симметричную версию алгоритмической локальной леммы Ловаса. Пусть $X_{1},\dots ,X_{n}$ — множество независимых в совокупности случайных величин ${\mathcal {P}}$ , которые выбираются равномерно и независимо друг от друга. Без ограничения общности можно считать, что в каждом дизъюнкте ровно $k$ литералов. «Плохим» в данной задаче будет событие $A_{i}$ , соответствующее тому, что $i$ -й дизъюнкт не выполнен. Поскольку каждый дизъюнкт содержит $k$ литералов (и, следовательно, $k$ переменных) и все переменные выбираются случайным образом, можно оценить вероятность каждого «плохого» события следующим образом:

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

Поскольку каждая переменная может появляться не более чем в ${\frac {2^{k}}{ke}}$ дизъюнктах, и в каждом дизъюнкте $k$ переменных, каждое «плохое» событие $A_{i}$ может зависеть не более чем от

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

других событий, следовательно

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

Если умножить обе стороны на $ep$ , получится

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

.

Из симметричной локальной леммы Ловаса следует, что вероятность реализации $X_{1},\dots ,X_{n}$ , при которой все дизъюнкты из $\Phi$ выполнены, не нулевая, и, следовательно, такая реализация должна существовать. Алгоритмическая лемма Ловаса позволяет найти такое присваивание за разумное время с помощью алгоритма, описанного выше. Алгоритм работает следующим образом:

Изначально берётся случайная реализация $X_{1},\dots ,X_{n}$ . Пока вся формула $\Phi$ не становится истинной, случайным образом выбирается невыполненный дизъюнкт $C$ из $\Phi$ , а затем всем переменным, которые встречаются в $C$ , присваиваются новые значения, которые выбираются равномерно случайным образом. Как только все дизъюнкты из $\Phi$ выполнены, алгоритм возвращает текущую реализацию. Следовательно, алгоритмическая локальная лемма Ловаса доказывает, что этот алгоритм будет работать не более чем за

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

шагов на формулах, которые удовлетворяют двум вышеуказанным условиям. Более сильная версия приведенного выше утверждения доказана Мозером[5], см. также работу Бирмана, Карпинского и Скотта[6].

Параллельная версия

Описанный выше алгоритм хорошо подходит для распараллеливания, так как параллельная генерация новых реализаций для событий $A,B\in {\mathcal {A}}$ таких, что ${\text{vbl}}(A)\cap {\text{vbl}}(B)=\emptyset$ , эквивалентна последовательной. Следовательно, на каждой итерации основного цикла можно определить максимальный набор независимых удовлетворенных событий $S$ и перегенерировать все события в $S$ параллельно.

Если набор $x$ удовлетворяет несколько более строгим условиям:

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

для некоторого $\varepsilon >0$ , то параллельный алгоритм даёт ожидаемое время исполнения порядка

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

.

Примечания

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.
ACM SIGACT - Gödel Prize (неопр.). sigact.org. Дата обращения: 20 апреля 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).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[moser:arxiv09-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:rsa91-2] 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.

[3] Former doctoral student Robin Moser receives prestigious Gödel Prize (англ.). ethz.ch. Дата обращения: 20 апреля 2020.

[4] ACM SIGACT - Gödel Prize (неопр.). sigact.org. Дата обращения: 20 апреля 2020.

[5] Moser, Robin A. (2008), A constructive proof of the Lovász Local Lemma, arΧiv:0810.4812 [cs.DS] .

[6] Piotr Berman, Marek Karpinski and Alexander D. Scott, Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT ], ECCC TR 03-022(2003).