Lema local algorítmico de Lovas

El lema local algorítmico de Lovas es un lema en informática teórica que permite construir objetos sujetos a ciertas restricciones.

Del lema local de Lovas se deduce que la probabilidad de que ninguno de los eventos de algún conjunto de eventos "malos" ocurra es estrictamente positiva si estos eventos satisfacen algunas restricciones adicionales. Al mismo tiempo, el lema no es constructivo y no permite construir explícitamente ejemplos de objetos para los que estos eventos no ocurren. En el caso de que estos eventos estén determinados por un conjunto finito de variables aleatorias independientes entre sí, el algoritmo del tipo Las Vegas con tiempo de ejecución polinomial desarrollado por los científicos Robin Moser y Gabor Tardos permite calcular explícitamente un determinado conjunto de valores de estas variables, para las cuales no existe ninguno de los eventos aleatorios considerados [1] . ${\ estilo de visualización \ {A_ {1}, \ puntos, A_ {n} \}}$

Una visión general del lema local de Lovas

El lema local de Lovas es una poderosa herramienta comúnmente utilizada en métodos probabilísticos para probar la existencia de algunos objetos matemáticos complejos con un conjunto de características dadas. Una prueba típica se reduce a considerar las propiedades de un objeto desde el punto de vista de la teoría de la probabilidad y usar el lema local de Lovas para estimar la probabilidad de ausencia de cualquiera de las características. La ausencia de un signo se considera un evento "malo", y si se puede demostrar que todos esos eventos "malos" pueden evitarse al mismo tiempo, entonces se prueba la existencia del objeto. El lema en sí se formula de la siguiente manera:

Sea un conjunto finito de eventos en el espacio de probabilidad . Para cualquier , let determina los vértices adyacentes al vértice en el gráfico de dependencia (en el gráfico de dependencia, el vértice es adyacente a eventos de los que no es independiente). Si hay un mapeo tal que ${\mathcal {A}}=\{A_{1},\ldots,A_{n}}\}$ $\Omega$ $A\in {\mathcal {A}}$ ${\ estilo de visualización \ 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)),

entonces la probabilidad de que ninguno de los eventos ocurra es positiva, es decir ${\mathcal {A}}$

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

Una versión algorítmica del lema local de Lovas

El lema local de Lovas no es constructivo porque permite inferir la existencia de propiedades estructurales u objetos complejos, pero no indica cómo se pueden encontrar o construir de manera eficiente en la práctica. En este caso, es probable que el muestreo aleatorio del espacio de probabilidad sea ineficiente, ya que la probabilidad del evento de interés es $\Omega$

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

limitado solo por el producto de pequeñas cantidades

\prod_{A\in {\mathcal {A}}}(1-x(A))

y por lo tanto es probable que sea muy pequeño.

Suponiendo que todos los eventos de están determinados por un conjunto finito de variables aleatorias mutuamente independientes de , Robin Moser y Gabor Tardos propusieron un algoritmo aleatorio eficiente que encuentra un conjunto de variables aleatorias en las que todos los eventos de no se cumplen. ${\mathcal {A}}$ ${\ matemáticas {P}}$ $\Omega$ ${\ matemáticas {P}}$ ${\mathcal {A}}$

Por lo tanto, este algoritmo se puede usar para construir de manera eficiente objetos complejos con características prescritas para la mayoría de los problemas a los que se aplica el lema local de Lovas.

Historia

El trabajo de Moser y Tardos estuvo precedido por otros resultados que permitieron avanzar en el desarrollo de versiones algorítmicas del lema local de Lovas. En 1991 , Joseph Beck demostró por primera vez que es posible, en principio, desarrollar una versión algorítmica del lema [2] . En su obra, la formulación del lema fue más rigurosa que en la definición no constructiva original. El enfoque de Beck requería que para cada , el número de dependencias estuviera acotado desde arriba como . La versión no constructiva del lema local admite una restricción más débil: $A\in {\mathcal {A}}$ $A$ $|\Gamma (A)|<2^{\frac {n}{48}}$

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

Esta estimación es inmejorable. El trabajo posterior cambió gradualmente esta estimación hasta que Moser y Tardos presentaron un algoritmo que lo logra.

En 2020, Robin Moser y Gabor Tardos recibieron el Premio Gödel por una versión algorítmica del lema local de Lovas [3] [4] .

Algoritmo

Sea la realización actual de la variable aleatoria , y sea la realización de todas las variables aleatorias desde . $v_{P}$ $P\in {\mathcal {P))$ $(v_{P})_{\mathcal {P))$ ${\ matemática P}$

El subconjunto mínimo único de variables aleatorias que determinan si ocurrirá un evento se denota por . ${\ matemáticas {P}}$ $A$ ${\text{vbl}}(A)$

Si el evento es verdadero al evaluar , decimos que la evaluación satisface , de lo contrario evita . $A$ $(v_{P})_{\mathcal {P))$ $(v_{P})_{\mathcal {P))$ $A$ $A$

El algoritmo funciona así:

Para cada valor , calcule aleatoriamente algo de su implementación $P\in {\mathcal {P))$ $v_{P}$
Siempre que haya uno que satisfaga : $A\in {\mathcal {A}}$ $(v_{P})_{\mathcal {P))$ $A$
- Seleccione un evento satisfecho arbitrario $A\in {\mathcal {A}}$
- Para cada cantidad , calcule una nueva realización $P\in {\text{vbl}}(A)$ $v_{P}$
Devolver $(v_{P})_{\mathcal {P))$

En la primera etapa, el algoritmo inicializa aleatoriamente la asignación actual para cada variable aleatoria . Esto significa que el valor se elige de forma aleatoria e independiente según la distribución de la variable aleatoria . Luego, el algoritmo ingresa al bucle principal, que se ejecuta hasta que se encuentra la implementación deseada. En cada iteración del bucle principal, el algoritmo selecciona un evento satisfecho arbitrario y vuelve a seleccionar todas las variables aleatorias que determinan . $v_{P}$ $P\in {\mathcal {P))$ $v_{P}$ $PAGS$ ${\mathcal {A}}$ ${\mathcal {A}}$

Teorema principal

Sea un conjunto finito de variables aleatorias independientes en la totalidad en el espacio de probabilidad , sea un conjunto finito de eventos determinados por estas variables. Si existe un conjunto tal que ${\ matemáticas {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))

entonces hay una implementación que evita todos los eventos de . Además, el algoritmo aleatorio descrito anteriormente vuelve a seleccionar un evento como máximo ${\ matemáticas {P}}$ ${\mathcal {A}}$ $A\in {\mathcal {A}}$

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

veces antes de que encuentre la implementación requerida. Por lo tanto, el tiempo de ejecución esperado del algoritmo no excede

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

[1] .

Versión simétrica

Los requisitos pueden parecer complejos y poco intuitivos. Pero puede ser reemplazada por tres condiciones simples: ${\ estilo de visualización x}$

$\forall A\in {\mathcal {A):|\Gamma (A)|\leq D$ , es decir, cada evento no depende más que de otros eventos; $A$ $D$
$\forall A\in {\mathcal {A}}:\Pr(A)\leq p$ , es decir, la probabilidad de cada evento no excede ; $A$ ${\ estilo de visualización p}$
$ep(D+1)\leq 1$ , donde es la base del logaritmo natural de . $mi$

Una variante del lema de Lovas local con estas tres condiciones en lugar de un conjunto se denomina lema de Lovas local simétrico. También es posible formular el lema local algorítmico simétrico de Lovas: ${\ estilo de visualización x}$

Sea un conjunto finito de variables aleatorias mutuamente independientes y sea un conjunto finito de eventos determinados por estas variables. Si se cumplen las tres condiciones anteriores, entonces hay una realización de los valores de que evita todos los eventos de . Además, el algoritmo aleatorio descrito anteriormente vuelve a seleccionar un evento no más de una vez antes de encontrar esa implementación. Por lo tanto, el tiempo de ejecución total esperado del algoritmo no excede . ${\ matemáticas {P}}$ $\mathcal{A}$ ${\ matemáticas {P}}$ ${\mathcal {A}}$ $A\in {\mathcal {A}}$ ${\frac{1}{D))$ ${\frac{n}{D))$

Ejemplo

El siguiente ejemplo muestra cómo se puede aplicar una versión algorítmica del lema local de Lovas a un problema simple.

Sea una forma normal conjuntiva de una fórmula sobre variables que contienen cláusulas y que tienen al menos literales en cada cláusula, y cada variable está presente en la mayoría de las cláusulas. Entonces factible . $\Fi$ ${\ estilo de visualización X_ {1}, \ puntos, X_ {n}}$ $norte$ $k$ $X_{yo}$ ${\frac{2^{k}}{ke}}$ $\Fi$

Esta afirmación se puede probar usando una versión simétrica del lema local algorítmico de Lovas. Sea un conjunto de variables aleatorias independientes , que se eligen de manera uniforme e independiente entre sí . Sin pérdida de generalidad, podemos suponer que hay exactamente literales en cada cláusula. El evento “malo” en esta tarea es el evento correspondiente al hecho de que la cláusula -ésima no se cumple. Dado que cada cláusula contiene literales (y, por lo tanto , variables) y todas las variables se eligen al azar, podemos estimar la probabilidad de cada evento "malo" de la siguiente manera: ${\ estilo de visualización X_ {1}, \ puntos, X_ {n}}$ ${\ matemáticas {P}}$ $k$ $Ai}$ $i$ $k$ $k$

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

Dado que cada variable puede aparecer en la mayoría de las cláusulas, y en cada cláusula de variables, cada evento "malo" puede depender de como máximo ${\frac{2^{k}}{ke}}$ $k$ $Ai}$

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

otros eventos, por lo que

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

Si multiplicas ambos lados por , obtienes ${\ episodio de estilo de visualización}$

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

Del lema local simétrico de Lovas se deduce que la probabilidad de una realización bajo la cual se satisfacen todas las cláusulas de no es cero y, por lo tanto, tal realización debe existir. El lema algorítmico de Lovas permite encontrar dicha asignación en un tiempo razonable utilizando el algoritmo descrito anteriormente. El algoritmo funciona así: ${\ estilo de visualización X_ {1}, \ puntos, X_ {n}}$ $\Fi$

Inicialmente, se toma una implementación aleatoria . Hasta que toda la fórmula sea verdadera, se selecciona aleatoriamente una cláusula insatisfecha de , y luego se asignan nuevos valores a todas las variables que ocurren en , que se eligen uniformemente al azar. Una vez que se cumplen todas las cláusulas de , el algoritmo devuelve la implementación actual. Por lo tanto, el lema local algorítmico de Lovas prueba que este algoritmo se ejecutará como máximo ${\ estilo de visualización X_ {1}, \ puntos, X_ {n}}$ $\Fi$ $C$ $\Fi$ $C$ $\Fi$

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

pasos en fórmulas que satisfacen las dos condiciones anteriores. Moser [5] demostró una versión más sólida de la declaración anterior , véase también Birman, Karpinski y Scott [6] .

Versión paralela

El algoritmo descrito anteriormente es muy adecuado para la paralelización, ya que la generación paralela de nuevas implementaciones para eventos como , es equivalente a la generación secuencial. Por lo tanto, en cada iteración del ciclo principal, es posible determinar el conjunto máximo de eventos satisfechos independientes y regenerar todos los eventos en paralelo. $A,B\in {\mathcal {A}}$ ${\text{vbl}}(A)\cap {\text{vbl}}(B)=\emptyset$ $S$ $S$

Si el conjunto satisface condiciones un poco más estrictas: $X$

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

para algunos , el algoritmo paralelo proporciona el tiempo de ejecución esperado de la orden $\varepsilon >0$

O\left({\frac {1}{\varepsilon }}\log \sum_{A\in {\mathcal {A}}}{\frac {x(A)}{1-x(A )}}\Correcto)

Notas

↑ 1 2 Moser, Robin A.; Tardós, Gabor. Una prueba constructiva del lema local general lovász (inglés) // Revista de la ACM : revista. - 2010. - Vol. 57 , núm. 2 . — Pág. 1 . -doi : 10.1145/ 1667053.1667060 . -arXiv : 0903.0544 . _
↑ Beck, József (1991), Un enfoque algorítmico del lema local de Lovász. I , Random Structures and Algorithms Vol. 2 (4): 343–366 , DOI 10.1002/rsa.3240020402 .
↑ El exestudiante de doctorado Robin Moser recibe el prestigioso Premio Gödel . ethz.ch. _ Consultado el 20 de abril de 2020. Archivado desde el original el 31 de octubre de 2021.
↑ ACM SIGACT-Premio Gödel . sigact.org . Consultado el 20 de abril de 2020. Archivado desde el original el 9 de enero de 2020. (indefinido)
↑ Moser, Robin A. (2008), Una prueba constructiva del lema local de Lovász, arΧiv : 0810.4812 [cs.DS]. .
↑ Piotr Berman, Marek Karpinski y Alexander D. Scott, Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT], ECCC TR 03-022(2003) Archivado el 3 de marzo de 2016 en Wayback Machine .