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 mediante la construcción de restricciones aleatorias de modo que, con una probabilidad no despreciable, exactamente una solución satisfaga estas restricciones adicionales si el espacio de la solución no está vacío. Los lemas de aislamiento tienen aplicaciones importantes en la 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 una probabilidad no despreciable, la intersección de cualquier espacio de solución fijo no vacío con los hiperplanos elegidos contiene exactamente un elemento. Esto es suficiente para mostrar el teorema de Valiant-Vazirani : existe una reducción aleatoria de tiempo polinomial desde el 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)introdujo 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 máximo de coincidencia .
En la literatura se han introducido lemas de aislamiento más fuertes para adaptarse a diferentes necesidades en diversos entornos. Por ejemplo, el lema de aislamiento de Chari, Rohatgi y Srinivasan (1993) tiene 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 las fórmulas k-CNF . Noam Ta-Shma [1] da un lema de aislamiento con parámetros ligeramente más fuertes y da resultados no triviales incluso cuando el tamaño del dominio de ponderación es menor que el número de variables.
El lema del aislamiento de Mulmuley, Vazirani y Vazirani
- Lema. Dejar y ser enteros positivos y dejar ser una familia arbitraria de subconjuntos del universo . Supongamos que cada elemento en el universo recibe un peso entero , cada uno de los cuales se elige de forma independiente y uniforme al azar de . El peso de un conjunto S en Se define como
- Entonces, con probabilidad al menos , hay un conjunto único en que tiene el peso mínimo entre todos los conjuntos de .
Es notable que el lema no asume nada sobre la naturaleza de la familia. : por ejemplo puede incluir todo 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í, es muy probable que exista un conjunto único que tenga un peso mínimo.
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, luego 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) de α , los conjuntos que no contienen x no disminuyen en peso, mientras que los que contienen x sí lo hacen). Por lo tanto, la ambigüedad acerca de 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 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 },
y la probabilidad de que algunos x es singular es como máximo n / N . Como hay un subconjunto único de peso mínimo si ningún elemento es singular, el lema sigue.
Observación: El lema se mantiene con (en lugar de =) ya que es posible que alguna 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).
Esta es una versión reafirmada de la prueba anterior, debida a Joel Spencer (1995). [2]
Para cualquier elemento x del conjunto, defina
Observa eso depende solo de los pesos de los elementos distintos de x , y no de w ( x ) en sí. Así que sea cual sea el valor de, como w ( x ) se elige uniformemente de {1,…, N }, la probabilidad de que sea igual aes como máximo de 1 / N . Por tanto, la probabilidad de quepara algunos x es como máximo n / N .
Ahora bien, si hay dos conjuntos A y B encon peso mínimo, entonces, tomando cualquier x en A \ B , tenemos
y como hemos visto, este evento ocurre con probabilidad 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 gráfico. A cada borde se le asigna un peso aleatorio en {1,…, 2 m } yes el conjunto de emparejamientos perfectos, de modo que con una probabilidad de al menos 1/2, existe un emparejamiento perfecto único. Cuando cada indeterminadoen la matriz de Tutte del gráfico se reemplaza con dónde es el peso aleatorio de la arista, podemos mostrar que el determinante de la matriz es distinto de cero y usarlo para encontrar la coincidencia.
- De manera más general, el documento también observó que cualquier problema de búsqueda de la forma "Dado un sistema establecido , encuentra un set en "podría reducirse a un problema de decisión de la forma" ¿Hay un conjunto en 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: y un subconjunto de los bordes marcados como "rojo", encuentra una combinación perfecta con exactamente k bordes rojos.
- El teorema de Valiant-Vazirani , que se refiere a soluciones únicas a problemas NP-completos, tiene una demostración más simple usando 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, por lo tanto, demostrar que NL / poli ⊆ ⊕L / poli. [4] Reinhardt y Allender usaron más tarde el lema del aislamiento nuevamente para demostrar que NL / poli = UL / poli. [5]
- El libro de Hemaspaandra y Ogihara tiene un capítulo sobre la técnica del aislamiento, que incluye generalizaciones. [6]
- El lema del aislamiento se ha propuesto como base de un esquema de 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
- ^ Noam Ta-Shma (2015); Una prueba 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). Desaleatorizar el lema de aislamiento y los límites inferiores para el tamaño del circuito . Actas del 11º taller internacional, APPROX 2008, y el 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 . Código bibliográfico : 2008arXiv0804.0957A . ISBN 978-3-540-85362-6. Consultado el 10 de mayo de 2010 .
- Arvind, V .; Mukhopadhyay, Partha; Srinivasan, Srikanth (2008). Nuevos resultados en pruebas de identidad polinomiales conmutativas y no conmutativas . Actas de la 23ª Conferencia Anual de IEEE 2008 sobre Complejidad Computacional. Sociedad de Informática IEEE. págs. 268-279. arXiv : 0801.0514 . Código bibliográfico : 2008arXiv0801.0514A . ISBN 978-0-7695-3169-4. Consultado el 10 de mayo de 2010 .
- Ben-David, S .; Chor, B .; Goldreich, O. (1989). Sobre la teoría de la complejidad media de los casos . Actas del vigésimo primer simposio anual de ACM sobre teoría de la computación - STOC '89. pag. 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 Sistemas . 74 (3): 386. doi : 10.1016 / j.jcss.2007.06.015 .
- Chari, S .; Rohatgi, P .; Srinivasan, A. (1993). Aislamiento de elementos únicos de aleatoriedad óptima, con aplicaciones para una combinación perfecta y problemas relacionados . Actas del vigésimo quinto simposio anual de ACM sobre teoría de la computación - STOC '93. pag. 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) . El compañero de la teoría de la complejidad . Saltador. ISBN 978-3-540-67419-1.
- Majumdar, Rupak; Wong, Jennifer L. (2001). Marca de agua de SAT utilizando lemas de aislamiento combinatorio . Actas de la 38ª Conferencia Anual de Automatización del Diseño. Las Vegas, Nevada, Estados Unidos: ACM. págs. 480–485. CiteSeerX 10.1.1.16.9300 . doi : 10.1145 / 378239.378566 . ISBN 1-58113-297-2.
- Reinhardt, K .; Allender, E. (2000). "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). "Emparejar es tan fácil como invertir la matriz". Combinatorica . 7 (1): 105-113. CiteSeerX 10.1.1.70.2247 . doi : 10.1007 / BF02579206 .
- Jukna, Stasys (2001). Combinatoria extrema: con aplicaciones en informática . Saltador. págs. 147-150. ISBN 978-3-540-66313-3.
- Valiant, L .; Vazirani, V. (1986). "NP es tan fácil como detectar soluciones únicas" (PDF) . Informática Teórica . 47 : 85–93. doi : 10.1016 / 0304-3975 (86) 90135-0 .
- Wigderson, Avi (1994). NL / poli ⊆ ⊕L / poli (PDF) . Actas de la 9ª Conferencia de Estructuras en Complejidad. págs. 59–62.
enlaces externos
- Teoremas favoritos: testigos únicos de Lance Fortnow
- El lema del aislamiento y más allá de Richard J. Lipton