lema de aislamiento

En informática teórica , el término lema de aislamiento (o lema aislante ) se refiere a algoritmos aleatorios que reducen el número de soluciones de un problema a una sola, si es que existe alguna. Esto se logra mediante la construcción de restricciones aleatorias tales que, con una probabilidad no despreciable, exactamente una solución satisface estas restricciones adicionales si el espacio de soluciones no está vacío. Los lemas de aislamiento tienen aplicaciones importantes en informática, como el teorema de Valiant-Vazirani y el teorema de Toda en la teoría de la complejidad computacional .

El primer lema de aislamiento fue introducido por Valiant y Vazirani (1986) , aunque no con ese nombre. Su lema de aislamiento elige un número aleatorio de hiperplanos aleatorios y tiene la propiedad de que, con probabilidad no despreciable, la intersección de cualquier espacio de soluciones fijo no vacío con los hiperplanos elegidos contiene exactamente un elemento. Esto basta para demostrar el teorema de Valiant-Vazirani : existe una reducción aleatoria en tiempo polinomial del problema de satisfacibilidad para fórmulas booleanas al problema de detectar si una fórmula booleana tiene una solución única. Mulmuley, Vazirani y Vazirani (1987) introdujeron un lema de aislamiento de un tipo ligeramente diferente: aquí, a cada coordenada del espacio de soluciones se le asigna un peso aleatorio en un cierto rango de enteros, y la propiedad es que, con probabilidad no despreciable, hay exactamente un elemento en el espacio de soluciones que tiene el peso mínimo. Esto puede usarse para obtener un algoritmo paralelo aleatorio para el problema de emparejamiento máximo .

En la literatura se han introducido lemas de aislamiento más robustos para adaptarse a diferentes necesidades en diversos contextos. Por ejemplo, el lema de aislamiento de Chari, Rohatgi y Srinivasan (1993) ofrece garantías similares a las de Mulmuley et al., pero utiliza menos bits aleatorios. En el contexto de la hipótesis del tiempo exponencial , Calabro et al. (2008) demuestran un lema de aislamiento para fórmulas k-CNF . Noam Ta-Shma ^{[ 1 ]} proporciona un lema de aislamiento con parámetros ligeramente más robustos y ofrece resultados no triviales incluso cuando el tamaño del dominio de pesos es menor que el número de variables.

El lema de aislamiento de Mulmuley, Vazirani y Vazirani

Lema. Dejemos

n

y

N

sean enteros positivos, y sea

{\mathcal {F}}

sea una familia arbitraria no vacía de subconjuntos del universo

\{1,\dots ,n\}

. Supongamos que cada elemento

x\in \{1,\dots ,n\}

en el universo recibe un peso entero

w(x)

, cada uno de los cuales se elige de forma independiente y uniforme al azar de

\{1,\dots ,N\}

. El peso de un conjunto S en

{\mathcal {F}}

se define como

w(S)=\sum _{x\in S}w(x)\,.

Entonces, con probabilidad al menos

1-n/N

, hay un conjunto único en

{\mathcal {F}}

que tiene el peso mínimo entre todos los conjuntos de

{\mathcal {F}}

.

Es notable que el lema no presuponga nada sobre la naturaleza de la familia. ${\mathcal {F}}$ : por ejemplo ${\mathcal {F}}$ puede incluir todos $2^{n}-1$ subconjuntos no vacíos. Dado que el peso de cada conjunto en ${\mathcal {F}}$ está entre $1$ y $nN$ en promedio habrá $(2^{n}-1)/(nN)$ conjuntos de cada peso posible. Aun así, con alta probabilidad , existe un único conjunto que tiene el peso mínimo.

La prueba de Mulmuley, Vazirani y Vazirani

Supongamos que hemos fijado los pesos de todos los elementos excepto un elemento x . Entonces x tiene un peso umbral α , tal que si el peso w ( x ) de x es mayor que α , entonces no está contenido en ningún subconjunto de peso mínimo, y si $w(x)\leq \alpha$ , entonces está contenido en algunos conjuntos de peso mínimo. Además, observe que si $w(x)<\alpha$ , entonces cada subconjunto de peso mínimo debe contener x (ya que, cuando disminuimos w(x) de α , los conjuntos que no contienen x no disminuyen en peso, mientras que los que contienen x sí). Por lo tanto, la ambigüedad sobre si un subconjunto de peso mínimo contiene x o no puede ocurrir solo cuando el peso de x es exactamente igual a su umbral; en este caso llamaremos a x "singular". Ahora bien, como el umbral de x se definió solo en términos de los pesos de los otros elementos, es independiente de w(x) y, por lo tanto, como w ( x ) se elige uniformemente de {1, …, N },

\Pr[x{\text{ es singular}}]=\Pr[w(x)=\alpha ]\leq 1/N

y la probabilidad de que algún x sea singular es como máximo n/N . Como existe un subconjunto único de peso mínimo si y solo si ningún elemento es singular, el lema se deduce.

Nota: El lema se cumple con $\leq$ (en lugar de =) ya que es posible que algún x no tenga un valor umbral (es decir, x no estará en ningún subconjunto de peso mínimo incluso si w ( x ) obtiene el valor mínimo posible, 1).

La prueba de Joel Spencer

Esta es una reformulación de la demostración anterior, debida a Joel Spencer (1995). ^{[ 2 ]}

Para cualquier elemento x del conjunto, defina

\alpha (x)=\min _{S\in {\mathcal {F}},x\not \in S}w(S)-\min _{S\in {\mathcal {F}},x\in S}w(S\setminus \{x\}).

Observa que $\alpha (x)$ depende únicamente de los pesos de los elementos distintos de x , y no de w ( x ) en sí mismo. Por lo tanto, cualquiera que sea el valor de $\alpha (x)$ , como w ( x ) se elige uniformemente de {1, …, N }, la probabilidad de que sea igual a $\alpha (x)$ es como máximo 1/ N . Por lo tanto, la probabilidad de que $w(x)=\alpha (x)$ para algún x es como máximo n/N .

Ahora bien, si hay dos conjuntos A y B en ${\mathcal {F}}$ con peso mínimo, entonces, tomando cualquier x en A\B , tenemos

{\begin{aligned}\alpha (x)&=\min _{S\in {\mathcal {F}},x\not \in S}w(S)-\min _{S\in {\mathcal {F}},x\in S}w(S\setminus \{x\})\\&=w(B)-(w(A)-w(x))\\&=w(x),\end{aligned}}

y como hemos visto, este evento ocurre con una probabilidad como máximo de n/N .

Ejemplos/aplicaciones

La aplicación original era para emparejamientos perfectos de peso mínimo (o peso máximo) en un grafo. A cada arista se le asigna un peso aleatorio en {1, …, 2 m }, y ${\mathcal {F}}$ es el conjunto de emparejamientos perfectos, de modo que con una probabilidad de al menos 1/2, existe un único emparejamiento perfecto . Cuando cada indeterminado $x_{ij}$ en la matriz de Tutte del gráfico se reemplaza por $2^{w_{ij}}$ dónde $w_{ij}$ es el peso aleatorio de la arista, podemos demostrar que el determinante de la matriz es distinto de cero, y además usar esto para encontrar el emparejamiento.
De manera más general, el artículo también observó que cualquier problema de búsqueda de la forma "Dado un conjunto de sistemas" $(S,{\mathcal {F}})$ , encontrar un conjunto en ${\mathcal {F}}$ " podría reducirse a un problema de decisión de la forma "¿Existe un conjunto en ${\mathcal {F}}$ con un peso total como máximo k ?". Por ejemplo, mostró cómo resolver el siguiente problema planteado por Papadimitriou y Yannakakis, para el cual (en el momento en que se escribió el artículo) no se conoce ningún algoritmo determinista de tiempo polinomial: dado un grafo y un subconjunto de las aristas marcadas como "rojas", encontrar un emparejamiento perfecto con exactamente k aristas rojas.
El teorema de Valiant-Vazirani , relativo a soluciones únicas para problemas NP-completos, tiene una demostración más sencilla mediante el lema de aislamiento. Esto se demuestra mediante una reducción aleatoria de CLIQUE a UNIQUE-CLIQUE. ^{[ 3 ]}
Ben-David, Chor y Goldreich (1989) utilizan la demostración de Valiant-Vazirani en su reducción de búsqueda a decisión para la complejidad del caso promedio .
Avi Wigderson utilizó el lema de aislamiento en 1994 para dar una reducción aleatoria de NL a UL y, por lo tanto, probar que NL/poly ⊆ ⊕L/poly. ^{[ 4 ]} Reinhardt y Allender posteriormente utilizaron nuevamente el lema de aislamiento para probar que NL/poly = UL/poly. ^{[ 5 ]}
El libro de Hemaspaandra y Ogihara tiene un capítulo sobre la técnica de aislamiento, incluyendo generalizaciones. ^{[ 6 ]}
El lema de aislamiento se ha propuesto como base de un esquema para la marca de agua digital . ^{[ 7 ]}
Se está trabajando en la eliminación de la aleatoriedad del lema de aislamiento en casos específicos ^{[ 8 ]} y en su uso para pruebas de identidad. ^{[ 9 ]}

Notas

↑ Noam Ta-Shma (2015); Una demostración simple del lema de aislamiento , en eccc
↑ Jukna (2001)
^ Mulmuley, Vazirani y Vazirani (1987)
↑ Wigderson (1994)
↑ Reinhardt y Allender (2000)
^ Hemaspaandra y Ogihara (2002)
↑ Majumdar y Wong (2001)
^ Arvind y Mukhopadhyay (2008)
^ Arvind, Mukhopadhyay y Srinivasan (2008)

Referencias

Arvind, V.; Mukhopadhyay, Partha (2008). Desaleatorización del lema de aislamiento y límites inferiores para el tamaño del circuito . Actas del 11.º taller internacional, APPROX 2008, y del 12.º taller internacional, RANDOM 2008, sobre aproximación, aleatorización y optimización combinatoria: algoritmos y técnicas. Boston, MA, EE. UU.: Springer-Verlag. págs. 276–289 . arXiv : 0804.0957 . Bibcode : 2008arXiv0804.0957A . ISBN 978-3-540-85362-6. Consultado el 10 de mayo de 2010 .
Arvind, V.; Mukhopadhyay, Partha; Srinivasan, Srikanth (2008). Nuevos resultados sobre la comprobación de identidad polinomial conmutativa y no conmutativa . Actas de la 23.ª Conferencia Anual de la IEEE sobre Complejidad Computacional de 2008. IEEE Computer Society. págs. 268–279 . arXiv : 0801.0514 . Bibcode : 2008arXiv0801.0514A . ISBN 978-0-7695-3169-4. Consultado el 10 de mayo de 2010 .
Ben-David, S.; Chor, B.; Goldreich, O. (1989). On the theory of average case complexity. Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89. p. 204. doi:10.1145/73007.73027. ISBN 0897913078.
Calabro, C.; Impagliazzo, R.; Kabanets, V.; Paturi, R. (2008). "The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs". Journal of Computer and System Sciences. 74 (3): 386. doi:10.1016/j.jcss.2007.06.015.
Chari, S.; Rohatgi, P.; Srinivasan, A. (1993). Randomness-optimal unique element isolation, with applications to perfect matching and related problems. Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93. p. 458. doi:10.1145/167088.167213. hdl:1813/6129. ISBN 0897915917.
Hemaspaandra, Lane A.; Ogihara, Mitsunori (2002). "Chapter 4. The Isolation Technique"(PDF). The complexity theory companion. Springer. ISBN 978-3-540-67419-1.
Majumdar, Rupak; Wong, Jennifer L. (2001). Watermarking of SAT using combinatorial isolation lemmas. Proceedings of the 38th annual Design Automation Conference. Las Vegas, Nevada, United States: ACM. pp. 480–485. CiteSeerX 10.1.1.16.9300. doi:10.1145/378239.378566. ISBN 1-58113-297-2.
Reinhardt, K.; Allender, E. (2000). "Making Nondeterminism Unambiguous"(PDF). SIAM Journal on Computing (FTP). p. 1118. doi:10.1137/S0097539798339041.(To view documents see Help:FTP)
Mulmuley, Ketan; Vazirani, Umesh; Vazirani, Vijay (1987). "Matching is as easy as matrix inversion". Combinatorica. 7 (1): 105–113. CiteSeerX 10.1.1.70.2247. doi:10.1007/BF02579206.
Jukna, Stasys (2001). Extremal combinatorics: with applications in computer science. Springer. pp. 147–150. ISBN 978-3-540-66313-3. Archived from the original on 2011-07-16. Retrieved 2010-05-09.
Valiant, L.; Vazirani, V. (1986). "NP es tan fácil como detectar soluciones únicas" (PDF) . Theoretical Computer Science . 47 : 85–93 . doi : 10.1016/0304-3975(86)90135-0 .
Wigderson, Avi (1994). NL/poly ⊆ ⊕L/poly (PDF) . Actas de la 9ª Conferencia sobre Estructuras en Complejidad. págs. 59–62 .

Enlaces externos

Teoremas favoritos: Testigos únicos , por Lance Fortnow
El lema del aislamiento y más allá, por Richard J. Lipton

[tashmaiso-1] Noam Ta-Shma (2015); Una demostración simple del lema de aislamiento , en eccc

[2] Jukna (2001)

[3] Mulmuley, Vazirani y Vazirani (1987)

[4] Wigderson (1994)

[5] Reinhardt y Allender (2000)

[6] Hemaspaandra y Ogihara (2002)

[7] Majumdar y Wong (2001)

[8] Arvind y Mukhopadhyay (2008)

[9] Arvind, Mukhopadhyay y Srinivasan (2008)

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]