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

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

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

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

Пусть ${\displaystyle {\mathcal {A}}=\{A_{1},\ldots ,A_{n}\}}$ — конечное множество событий в вероятностном пространстве ${\displaystyle \Omega }$. Для любого ${\displaystyle A\in {\mathcal {A}}}$ пусть ${\displaystyle \Gamma (A)}$ определяет смежные с ${\displaystyle A}$ вершины в графе зависимостей (в графе зависимостей вершина ${\displaystyle A}$ смежна с событиями, от которых она не независима). Если существует отображение ${\displaystyle x:{\mathcal {A}}\to (0,1)}$ такое, что

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

то вероятность того, что ни одно из событий ${\displaystyle {\mathcal {A}}}$ не произойдет, положительна, а именно

${\displaystyle \Pr \left({\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right)\geq \prod \limits _{i\in \{1,\dots ,n\}}(1-x(A_{i})).}$

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

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

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

${\displaystyle \prod _{A\in {\mathcal {A}}}(1-x(A))}$ и поэтому, вероятно, будет очень мала.

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

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

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

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

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

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

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

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

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

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

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

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

Пусть ${\displaystyle {\mathcal {P}}}$ — конечное множество независимых в совокупности случайных величин в вероятностном пространстве ${\displaystyle \Omega }$, ${\displaystyle {\mathcal {A}}}$ — конечное множество событий, определяемых этими величинами. Если существует набор ${\displaystyle x:{\mathcal {A}}\to (0,1)}$ такой, что

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

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

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

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

${\displaystyle \sum _{A\in {\mathcal {A}}}{\frac {x(A)}{1-x(A)}}}$^[1].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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