En informática , un algoritmo holográfico es un algoritmo que utiliza una reducción holográfica. Una reducción holográfica es una reducción de tiempo constante que asigna fragmentos de solución de muchos a muchos de modo que la suma de los fragmentos de solución permanece inalterada. Estos conceptos fueron introducidos por Leslie Valiant , quien los llamó holográficos porque "su efecto puede verse como el de producir patrones de interferencia entre los fragmentos de solución". [1] Los algoritmos no están relacionados con la holografía láser , excepto metafóricamente. Su poder proviene de la cancelación mutua de muchas contribuciones a una suma, análoga a los patrones de interferencia en un holograma. [2]
Los algoritmos holográficos se han utilizado para encontrar soluciones en tiempo polinomial a problemas sin tales soluciones conocidas previamente para casos especiales de satisfacibilidad , cobertura de vértices y otros problemas de grafos . [3] Han recibido una cobertura notable debido a la especulación de que son relevantes para el problema P versus NP [2] y su impacto en la teoría de la complejidad computacional . Aunque algunos de los problemas generales son problemas #P-hard , los casos especiales resueltos no son en sí mismos #P-hard y, por lo tanto, no prueban que FP = #P.
Los algoritmos holográficos tienen algunas similitudes con la computación cuántica , pero son completamente clásicos. [4]
Los algoritmos holográficos existen en el contexto de los problemas de Holant, que generalizan los problemas de satisfacción de restricciones de conteo (#CSP). Una instancia de #CSP es un hipergrafo G = ( V , E ) llamado grafo de restricciones . Cada hiperarista representa una variable y a cada vértice se le asigna una restricción. Un vértice está conectado a una hiperarista si la restricción en el vértice involucra a la variable en la hiperarista. El problema de conteo es calcular
que es una suma de todas las asignaciones de variables, el producto de cada restricción, donde las entradas a la restricción son las variables en los hiperbordes incidentes de .
Un problema de Holant es como un #CSP excepto que la entrada debe ser un gráfico, no un hipergráfico. Restringir la clase de gráficos de entrada de esta manera es, de hecho, una generalización. Dada una instancia de #CSP, reemplace cada hiperarista e de tamaño s con un vértice v de grado s con aristas incidentes a los vértices contenidos en e . La restricción en v es la función de igualdad de aridad s . Esto identifica todas las variables en las aristas incidentes a v , que es el mismo efecto que la variable única en la hiperarista e .
En el contexto de los problemas de Holant, la expresión en (1) se denomina Holant en honor a una suma exponencial relacionada introducida por Valiant. [5]
Una técnica estándar en la teoría de la complejidad es la reducción de muchos-uno , en la que una instancia de un problema se reduce a una instancia de otro problema (con suerte, más simple). Sin embargo, las reducciones holográficas entre dos problemas computacionales preservan la suma de soluciones sin preservar necesariamente las correspondencias entre soluciones. [1] Por ejemplo, se puede preservar el número total de soluciones en ambos conjuntos, aunque los problemas individuales no tengan soluciones coincidentes. La suma también se puede ponderar, en lugar de simplemente contar el número de soluciones, utilizando vectores de base lineales . [3]
Es conveniente considerar reducciones holográficas en grafos bipartitos. Un grafo general siempre se puede transformar en un grafo bipartito conservando el valor de Holant. Esto se hace reemplazando cada arista del grafo por un camino de longitud 2, que también se conoce como el estiramiento 2 del grafo. Para mantener el mismo valor de Holant, a cada nuevo vértice se le asigna la restricción de igualdad binaria.
Considere un grafo bipartito G = ( U , V , E ) donde la restricción asignada a cada vértice es y la restricción asignada a cada vértice es . Denote este problema de conteo por Si los vértices en U se ven como un gran vértice de grado | E |, entonces la restricción de este vértice es el producto tensorial de consigo mismo | U | veces, que se denota por Del mismo modo, si los vértices en V se ven como un gran vértice de grado | E |, entonces la restricción de este vértice es Sea la restricción representada por su tabla de verdad ponderada como un vector fila y la restricción representada por su tabla de verdad ponderada como un vector columna. Entonces el Holant de este grafo de restricción es simplemente
Ahora bien, para cualquier matriz invertible compleja de 2 por 2 T (cuyas columnas son los vectores base lineales mencionados anteriormente), existe una reducción holográfica entre y Para ver esto, inserte la matriz identidad en el medio para obtener
Por lo tanto, y tienen exactamente el mismo valor de Holant para cada gráfico de restricción. Básicamente, definen el mismo problema de conteo.
Sea G un grafo. Existe una correspondencia biunívoca entre los recubrimientos de vértices de G y los conjuntos independientes de G. Para cualquier conjunto S de vértices de G , S es un recubrimiento de vértices en G si y solo si el complemento de S es un conjunto independiente en G. Por lo tanto, el número de recubrimientos de vértices en G es exactamente el mismo que el número de conjuntos independientes en G.
La equivalencia de estos dos problemas de conteo también se puede demostrar utilizando una reducción holográfica. Para simplificar, sea G un grafo regular 3- . El estiramiento 2- de G da un grafo bipartito H = ( U , V , E ), donde U corresponde a las aristas en G y V corresponde a los vértices en G . El problema de Holant que corresponde naturalmente a contar el número de cubiertas de vértices en G es La tabla de verdad de OR 2 como un vector fila es (0,1,1,1). La tabla de verdad de EQUAL 3 como un vector columna es . Entonces bajo una transformación holográfica por
que es el problema de Holant que naturalmente corresponde a contar el número de conjuntos independientes en G.
Al igual que con cualquier tipo de reducción, una reducción holográfica no produce, por sí misma, un algoritmo de tiempo polinomial. Para obtener un algoritmo de tiempo polinomial, el problema al que se reduce también debe tener un algoritmo de tiempo polinomial. La aplicación original de Valiant de los algoritmos holográficos utilizó una reducción holográfica a un problema en el que cada restricción es realizable por medio de puertas de coincidencia, [1] que acababa de demostrar que es manejable mediante una reducción adicional para contar el número de coincidencias perfectas en un grafo planar . [6] El último problema es manejable mediante el algoritmo FKT , que data de la década de 1960.
Poco después, Valiant encontró algoritmos holográficos con reducciones a matchgates para # 7 Pl -Rtw- Mon -3 CNF y # 7 Pl-3/2 Bip - VC . [7] Estos problemas pueden parecer algo artificiales, especialmente con respecto al módulo . Ya se sabía que ambos problemas eran # P-duros cuando se ignoraba el módulo y Valiant proporcionó pruebas de # P-dureza módulo 2, que también usaban reducciones holográficas. Valiant encontró estos dos problemas mediante una búsqueda por computadora que buscaba problemas con reducciones holográficas a matchgates. Llamó a sus algoritmos algoritmos accidentales , diciendo "al aplicar el término accidental a un algoritmo pretendemos señalar que el algoritmo surge de satisfacer un conjunto aparentemente oneroso de restricciones". El conjunto "oneroso" de restricciones en cuestión son ecuaciones polinómicas que, si se satisfacen, implican la existencia de una reducción holográfica a restricciones realizables de matchgate.
Después de varios años de desarrollar (lo que se conoce como) teoría de firma de matchgate, Jin-Yi Cai y Pinyan Lu pudieron explicar la existencia de los dos algoritmos accidentales de Valiant. [3] Estos dos problemas son solo casos especiales de dos familias mucho más grandes de problemas: # 2 k -1 Pl-Rtw-Mon-kCNF y # 2 k -1 Pl-k/2Bip-VC para cualquier entero positivo k . El módulo 7 es solo el tercer número de Mersenne y Cai y Lu demostraron que estos tipos de problemas con parámetro k se pueden resolver en tiempo polinomial exactamente cuando el módulo es el k ésimo número de Mersenne mediante el uso de reducciones holográficas para matchgates y el teorema del resto chino .
Casi al mismo tiempo, Jin-Yi Cai, Pinyan Lu y Mingji Xia dieron el primer algoritmo holográfico que no se reducía a un problema que se pudiera tratar con puertas de coincidencia. [5] En cambio, redujeron a un problema que se puede tratar con puertas de Fibonacci, que son restricciones simétricas cuyas tablas de verdad satisfacen una relación de recurrencia similar a la que define los números de Fibonacci . También utilizaron reducciones holográficas para demostrar que ciertos problemas de conteo son #P-hard. Desde entonces, las reducciones holográficas se han utilizado ampliamente como ingredientes tanto en algoritmos de tiempo polinomial como en pruebas de #P-hardness.
