Lema de aislamiento

Técnica para reducir el número de soluciones

En informática teórica , el término lema de aislamiento (o lema de aislamiento ) se refiere a algoritmos aleatorios que reducen el número de soluciones a un problema a una, en caso de que exista una solución. Esto se logra construyendo restricciones aleatorias de manera que, con una probabilidad no despreciable, exactamente una solución satisfaga 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 bajo ese nombre. Su lema de aislamiento elige un número aleatorio de hiperplanos aleatorios y tiene la propiedad de que, con una probabilidad no despreciable, la intersección de cualquier espacio de solución no vacío fijo con los hiperplanos elegidos contiene exactamente un elemento. Esto es suficiente 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 solución se le asigna un peso aleatorio en un cierto rango de números enteros y la propiedad es que, con una probabilidad no despreciable, hay exactamente un elemento en el espacio de solución que tiene un peso mínimo. Esto se puede utilizar para obtener un algoritmo paralelo aleatorio para el problema de emparejamiento máximo .

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

El lema de aislamiento de Mulmuley, Vazirani y Vazirani

Cualquier programa lineal con una función de costo lineal elegida aleatoriamente tiene un óptimo único con alta probabilidad. El lema de aislamiento de Mulmuley, Vazirani y Vazirani extiende este hecho a conjuntos arbitrarios y una función de costo aleatoria que se muestrea utilizando unos pocos bits aleatorios.

Lema. Sean y números enteros positivos, y sea una familia arbitraria no vacía de subconjuntos del universo . Supóngase que cada elemento del universo recibe un peso entero , cada uno de los cuales se elige de forma independiente y uniforme al azar entre . El peso de un conjunto S en se define como ${\displaystyle n}$ ${\displaystyle N}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \{1,\dots ,n\}}$ ${\displaystyle x\in \{1,\dots ,n\}}$ ${\displaystyle w(x)}$ ${\displaystyle \{1,\dots ,N\}}$ ${\displaystyle {\mathcal {F}}}$

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

Entonces, con una probabilidad de al menos , hay un conjunto único en que tiene el peso mínimo entre todos los conjuntos de . ${\displaystyle 1-n/N}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$

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

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 , entonces está contenido en algunos conjuntos de peso mínimo. Además, observe que si , entonces cada subconjunto de peso mínimo debe contener x (ya que, cuando disminuimos w(x) a partir de α , los conjuntos que no contienen a x no disminuyen en peso, mientras que los que contienen a x sí). Por lo tanto, la ambigüedad sobre si un subconjunto de peso mínimo contiene a 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, 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 }, ${\displaystyle w(x)\leq \alpha }$ ${\displaystyle w(x)<\alpha }$

${\displaystyle \Pr[x{\text{ is 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 hay un único subconjunto de peso mínimo si y solo si ningún elemento es singular, se sigue el lema.

Observación: El lema se cumple con (en lugar de =) ya que es posible que algún x no tenga 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). ${\displaystyle \leq }$

La prueba de Joel Spencer

Esta es una versión reformulada de la prueba anterior, debida a Joel Spencer (1995). ^[2]

Para cualquier elemento x del conjunto, define

${\displaystyle \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\}).}$

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

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

${\displaystyle {\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 de como máximo  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 es el conjunto de emparejamientos perfectos, de modo que con una probabilidad de al menos 1/2, existe un emparejamiento perfecto único. Cuando cada indeterminado en la matriz de Tutte del grafo se reemplaza por donde es el peso aleatorio de la arista, podemos demostrar que el determinante de la matriz es distinto de cero, y luego usar esto para encontrar el emparejamiento. ${\displaystyle {\mathcal {F}}}$ ${\displaystyle x_{ij}}$ ${\displaystyle 2^{w_{ij}}}$ ${\displaystyle w_{ij}}$
• En términos más generales, el artículo también observó que cualquier problema de búsqueda de la forma "Dado un sistema de conjuntos , encuentre un conjunto en " podría reducirse a un problema de decisión de la forma "¿Existe un conjunto en con un peso total de k como máximo ?". Por ejemplo, mostró cómo resolver el siguiente problema planteado por Papadimitriou y Yannakakis, para el cual (al momento en que se escribió el artículo) no se conocía ningún algoritmo de tiempo polinomial determinista: dado un grafo y un subconjunto de los bordes marcados como "rojos", encuentre una coincidencia perfecta con exactamente k bordes rojos. ${\displaystyle (S,{\mathcal {F}})}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$
• El teorema de Valiant-Vazirani , que se refiere a soluciones únicas para problemas NP-completos, tiene una demostración más sencilla mediante el lema de aislamiento. Esto se demuestra dando una reducción aleatoria de CLIQUE a UNIQUE-CLIQUE. ^[3]
• Ben-David, Chor y Goldreich (1989) utilizan la prueba 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 así demostrar que NL/poly ⊆ ⊕L/poly. ^[4] Reinhardt y Allender utilizaron más tarde el lema de aislamiento nuevamente para demostrar 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 desaleatorización del lema de aislamiento en casos específicos ^[8] y en su uso para pruebas de identidad. ^[9]

Notas

1. Noam Ta-Shma (2015); Una prueba 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)

Referencias

• Arvind, V.; Mukhopadhyay, Partha (2008). Desrandomizació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. pp. 276–289. arXiv : 0804.0957 . Código Bibliográfico :2008arXiv0804.0957A. ISBN 978-3-540-85362-6. Recuperado el 10 de mayo de 2010 .
• Arvind, V.; Mukhopadhyay, Partha; Srinivasan, Srikanth (2008). Nuevos resultados sobre pruebas de identidad polinómica conmutativa y no conmutativa. Actas de la 23.ª Conferencia Anual sobre Complejidad Computacional del IEEE de 2008. IEEE Computer Society. págs. 268–279. arXiv : 0801.0514 . Código Bibliográfico :2008arXiv0801.0514A. ISBN . 978-0-7695-3169-4. Recuperado el 10 de mayo de 2010 .
• Ben-David, S.; Chor, B .; Goldreich, O. (1989). Sobre la teoría de la complejidad de los casos promedio . Actas del vigésimo primer simposio anual de la ACM sobre teoría de la computación - STOC '89. p. 204. doi :10.1145/73007.73027. ISBN 0897913078.
• Calabro, C.; Impagliazzo, R.; Kabanets, V.; Paturi, R. (2008). "La complejidad de k-SAT único: un lema de aislamiento para k-CNF". Revista de Ciencias de la Computación y de Sistemas . 74 (3): 386. doi : 10.1016/j.jcss.2007.06.015 .
• Chari, S.; Rohatgi, P.; Srinivasan, A. (1993). Aislamiento de elementos únicos con aleatoriedad óptima, con aplicaciones para problemas de emparejamiento perfecto y relacionados . Actas del vigésimo quinto simposio anual de la ACM sobre teoría de la computación - STOC '93. pág. 458. doi :10.1145/167088.167213. hdl : 1813/6129 . ISBN . 0897915917.
• Hemaspaandra, Lane A.; Ogihara, Mitsunori (2002). "Capítulo 4. La técnica de aislamiento" (PDF) . The complex theory companion . Springer. ISBN 978-3-540-67419-1.
• Majumdar, Rupak; Wong, Jennifer L. (2001). Marcas de agua de SAT usando lemas de aislamiento combinatorio . Actas de la 38.ª Conferencia Anual de Automatización del Diseño. Las Vegas, Nevada, Estados Unidos: 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). "Cómo hacer que el no determinismo sea inequívoco" (PDF) . Revista SIAM de Computación . 29 (4): 1118. doi :10.1137/S0097539798339041.
• Mulmuley, Ketan ; Vazirani, Umesh ; Vazirani, Vijay (1987). "Hacer coincidir es tan fácil como invertir matrices". Combinatoria . 7 (1): 105-113. CiteSeerX  10.1.1.70.2247 . doi :10.1007/BF02579206.
• Jukna, Stasys (2001). Combinatoria extrema: con aplicaciones en informática. Springer. pp. 147–150. ISBN 978-3-540-66313-3.
• 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 de Lance Fortnow
• El lema del aislamiento y más allá, por Richard J. Lipton