Hispanopedia Wiki
Articulo de referencia

Algoritmo holográfico

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 mapea fragmen...

Hispanopedia WikiContenido en espanolLectura gratuita

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 mapea fragmentos de solución de muchos a muchos, de manera que la suma de los fragmentos de solución permanece inalterada. Estos conceptos fueron introducidos por Leslie Valiant , quien los denominó holográficos porque "su efecto puede considerarse como la producción de patrones de interferencia entre los fragmentos de solución". [ 1 ] Los algoritmos no guardan relación con la holografía láser , salvo metafóricamente. Su poder reside en la cancelación mutua de múltiples 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 de tiempo polinomial a problemas sin soluciones previamente conocidas 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-difíciles , los casos especiales resueltos no son en sí mismos #P-difíciles y, por lo tanto, no prueban FP = #P.

Los algoritmos holográficos tienen algunas similitudes con la computación cuántica , pero son completamente clásicos. [ 4 ]

Problemas de Holant

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 cada vérticev{\displaystyle v}se le asigna una restricciónFv.{\displaystyle f_{v}.}Un vértice está conectado a una hiperarista si la restricción sobre el vértice involucra la variable en la hiperarista. El problema de conteo consiste en calcular

∑σ:mi→{0,1}∏v∈VFv(σ|mi(v)),          (1){\displaystyle \sum _{\sigma :E\to \{0,1\}}\prod _{v\in V}f_{v}(\sigma |_{E(v)}),~~~~~~~~~~(1)}

que es una suma sobre todas las asignaciones de variables, el producto de cada restricción, donde las entradas a la restricciónFv{\displaystyle f_{v}}son las variables en los hiperbordes incidentes dev{\displaystyle v}.

Un problema de Holant es como un #CSP excepto que la entrada debe ser un grafo, no un hipergrafo. Restringir la clase de grafos de entrada de esta manera es, de hecho, una generalización. Dada una instancia de #CSP, reemplazamos 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 sobre v es la función de igualdad de aridad s . Esto identifica todas las variables en las aristas incidentes a v , lo que tiene 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 llama Holant en honor a una suma exponencial relacionada introducida por Valiant. [ 5 ]

Reducción holográfica

Una técnica estándar en la teoría de la complejidad es la reducción muchos-uno , donde una instancia de un problema se reduce a una instancia de otro problema (preferiblemente más simple). Sin embargo, las reducciones holográficas entre dos problemas computacionales conservan la suma de las soluciones sin necesariamente conservar las correspondencias entre ellas. [ 1 ] Por ejemplo, se puede conservar el número total de soluciones en ambos conjuntos, incluso si los problemas individuales no tienen soluciones coincidentes. La suma también puede ponderarse, en lugar de simplemente contar el número de soluciones, utilizando vectores base lineales . [ 3 ]

Ejemplo general

Resulta conveniente considerar las reducciones holográficas en grafos bipartitos. Un grafo general siempre puede transformarse en un grafo bipartito conservando el valor de Holant. Esto se logra reemplazando cada arista del grafo por un camino de longitud 2, también conocido 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.

Consideremos un grafo bipartito G = ( U , V , E ) donde la restricción asignada a cada vérticetú∈U{\displaystyle u\in U}esFtú{\displaystyle f_{u}}y la restricción asignada a cada vérticev∈V{\displaystyle v\in V}esFv{\displaystyle f_{v}}Denotemos este problema de conteo porHolant(GRAMO,Ftú,Fv).{\displaystyle {\text{Holant}}(G,f_{u},f_{v}).}Si los vértices en U se consideran como un único vértice grande de grado | E |, entonces la restricción de este vértice es el producto tensorial deFtú{\displaystyle f_{u}}con sí mismo | U | veces, lo cual se denota porFtú⊗|U|.{\displaystyle f_{u}^{\otimes |U|}.}Asimismo, si los vértices en V se consideran como un único vértice grande de grado | E |, entonces la restricción de este vértice esFv⊗|V|.{\displaystyle f_{v}^{\otimes |V|}.}Sea la restricciónFtú{\displaystyle f_{u}}estar representado por su tabla de verdad ponderada como un vector fila y la restricciónFv{\displaystyle f_{v}}estar representado por su tabla de verdad ponderada como un vector columna. Entonces, el Holant de este grafo de restricciones es simplementeFtú⊗|U|Fv⊗|V|.{\displaystyle f_{u}^{\otimes |U|}f_{v}^{\otimes |V|}.}

Ahora bien, para cualquier matriz invertible compleja de 2x2 T (cuyas columnas son los vectores base lineales mencionados anteriormente), existe una reducción holográfica entreHolant(GRAMO,Ftú,Fv){\displaystyle {\text{Holant}}(G,f_{u},f_{v})}yHolant(GRAMO,FtúT⊗(grados⁡tú),(T−1)⊗(grados⁡v)Fv).{\displaystyle {\text{Holant}}(G,f_{u}T^{\otimes (\deg u)},(T^{-1})^{\otimes (\deg v)}f_{v}).}Para ver esto, inserte la matriz identidad.T⊗|mi|(T−1)⊗|mi|{\displaystyle T^{\otimes |E|}(T^{-1})^{\otimes |E|}}entreFtú⊗|U|Fv⊗|V|{\displaystyle f_{u}^{\otimes |U|}f_{v}^{\otimes |V|}}Llegar

Ftú⊗|U|Fv⊗|V|{\displaystyle f_{u}^{\otimes |U|}f_{v}^{\otimes |V|}}
=Ftú⊗|U|T⊗|mi|(T−1)⊗|mi|Fv⊗|V|{\displaystyle =f_{u}^{\otimes |U|}T^{\otimes |E|}(T^{-1})^{\otimes |E|}f_{v}^{\otimes |V|}}
=(FtúT⊗(grados⁡tú))⊗|U|(Fv(T−1)⊗(grados⁡v))⊗|V|.{\displaystyle =\left(f_{u}T^{\otimes (\deg u)}\right)^{\otimes |U|}\left(f_{v}(T^{-1})^{\otimes (\deg v)}\right)^{\otimes |V|}.}

De este modo,Holant(GRAMO,Ftú,Fv){\displaystyle {\text{Holant}}(G,f_{u},f_{v})}yHolant(GRAMO,FtúT⊗(grados⁡tú),(T−1)⊗(grados⁡v)Fv){\displaystyle {\text{Holant}}(G,f_{u}T^{\otimes (\deg u)},(T^{-1})^{\otimes (\deg v)}f_{v})}Tienen exactamente el mismo valor de Holant para cada grafo de restricciones. En esencia, definen el mismo problema de conteo.

Ejemplos específicos

Recubrimientos de vértices y conjuntos independientes

Sea G un grafo. Existe una correspondencia biunívoca entre las cubiertas de vértices de G y los conjuntos independientes de G. Para cualquier conjunto S de vértices de G , S es una cubierta 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 cubiertas de vértices en G es exactamente igual al 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 3-regular . 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 esHolant(H,O2,IGUAL3).{\displaystyle {\text{Holant}}(H,{\text{OR}}_{2},{\text{EQUAL}}_{3}).}La tabla de verdad de OR 2 como vector fila es (0,1,1,1). La tabla de verdad de EQUAL 3 como vector columna es(1,0,0,0,0,0,0,1)T=[10]⊗3+[01]⊗3{\displaystyle (1,0,0,0,0,0,0,1)^{T}={\begin{bmatrix}1\\0\end{bmatrix}}^{\otimes 3}+{\begin{bmatrix}0\\1\end{bmatrix}}^{\otimes 3}}Luego, bajo una transformación holográfica por[0110],{\displaystyle {\begin{bmatrix}0&1\\1&0\end{bmatrix}},}

O2⊗|U|IGUAL3⊗|V|{\displaystyle {\text{OR}}_{2}^{\otimes |U|}{\text{EQUAL}}_{3}^{\otimes |V|}}
=(0,1,1,1)⊗|U|([10]⊗3+[01]⊗3)⊗|V|{\displaystyle =(0,1,1,1)^{\otimes |U|}\left({\begin{bmatrix}1\\0\end{bmatrix}}^{\otimes 3}+{\begin{bmatrix}0\\1\end{bmatrix}}^{\otimes 3}\right)^{\otimes |V|}}
=(0,1,1,1)⊗|U|[0110]⊗|mi|[0110]⊗|mi|([10]⊗3+[01]⊗3)⊗|V|{\displaystyle =(0,1,1,1)^{\otimes |U|}{\begin{bmatrix}0&1\\1&0\end{bmatrix}}^{\otimes |E|}{\begin{bmatrix}0&1\\1&0\end{bmatrix}}^{\otimes |E|}\left({\begin{bmatrix}1\\0\end{bmatrix}}^{\otimes 3}+{\begin{bmatrix}0\\1\end{bmatrix}}^{\otimes 3}\right)^{\otimes |V|}}
=((0,1,1,1)[0110]⊗2)⊗|U|(([0110][10])⊗3+([0110][01])⊗3)⊗|V|{\displaystyle =\left((0,1,1,1){\begin{bmatrix}0&1\\1&0\end{bmatrix}}^{\otimes 2}\right)^{\otimes |U|}\left(\left({\begin{bmatrix}0&1\\1&0\end{bmatrix}}{\begin{bmatrix}1\\0\end{bmatrix}}\right)^{\otimes 3}+\left({\begin{bmatrix}0&1\\1&0\end{bmatrix}}{\begin{bmatrix}0\\1\end{bmatrix}}\right)^{\otimes 3}\right)^{\otimes |V|}}
=(1,1,1,0)⊗|U|([01]⊗3+[10]⊗3)⊗|V|{\displaystyle =(1,1,1,0)^{\otimes |U|}\left({\begin{bmatrix}0\\1\end{bmatrix}}^{\otimes 3}+{\begin{bmatrix}1\\0\end{bmatrix}}^{\otimes 3}\right)^{\otimes |V|}}
=NAND2⊗|U|IGUAL3⊗|V|,{\displaystyle ={\text{NAND}}_{2}^{\otimes |U|}{\text{EQUAL}}_{3}^{\otimes |V|},}

que esHolant(H,NAND2,IGUAL3),{\displaystyle {\text{Holant}}(H,{\text{NAND}}_{2},{\text{EQUAL}}_{3}),}el problema de Holant que corresponde naturalmente a contar el número de conjuntos independientes en G.

Historia

Como ocurre con cualquier tipo de reducción, una reducción holográfica no produce, por sí sola, 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 donde cada restricción es realizable por matchgates , [ 1 ] que acababa de demostrar que es tratable mediante una reducción adicional al conteo del número de emparejamientos perfectos en un grafo planar . [ 6 ] Este último problema es tratable 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-difíciles cuando se ignoraba el módulo y Valiant proporcionó pruebas de #P-dificultad módulo 2, que también utilizaban reducciones holográficas. Valiant encontró estos dos problemas mediante una búsqueda computarizada que buscaba problemas con reducciones holográficas a matchgates. Llamó a sus algoritmos algoritmos accidentales , diciendo "cuando aplicamos el término accidental a un algoritmo pretendemos señalar que el algoritmo surge de satisfacer un conjunto de restricciones aparentemente onerosas". El conjunto de restricciones "onerosas" 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 firmas 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 de problemas mucho más grandes: # 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 este tipo de problemas con parámetro k se pueden resolver en tiempo polinomial exactamente cuando el módulo es el k th número de Mersenne usando reducciones holográficas a matchgates y el teorema chino del resto .

Casi al mismo tiempo, Jin-Yi Cai, Pinyan Lu y Mingji Xia presentaron el primer algoritmo holográfico que no se redujo a un problema tratable mediante compuertas de coincidencia. [ 5 ] En cambio, lo redujeron a un problema tratable mediante compuertas 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-difíciles. Desde entonces, las reducciones holográficas se han utilizado ampliamente como ingredientes tanto en algoritmos de tiempo polinomial como en demostraciones de #P-dificultad.

Referencias

  1. 1 2 3 Valiant, Leslie (17–19 de octubre de 2004). Algoritmos holográficos (Resumen extendido) . FOCS 2004. Roma, Italia: IEEE Computer Society. págs. 306–315 . doi : 10.1109/FOCS.2004.34 . ISBN  0-7695-2228-9Archivado del original el 13 de marzo de 2012. Consultado el 27 de febrero de 2011 .
  2. 1 2 Hayes, Brian (enero-febrero de 2008). "Algoritmos accidentales" . American Scientist .
  3. 1 2 3 Cai, Jin-Yi; Lu, Pinyan (2011). "Algoritmos holográficos: Del arte a la ciencia" . J. Comput. Syst. Sci . 77 (1): 41– 61. doi : 10.1016/j.jcss.2010.06.005 .
  4. ^ Cai, Jin-Yi (junio de 2008). "Algoritmos holográficos: columna de invitados". Noticias SIGACT . 39 (2). Nueva York, NY, EE. UU.: ACM: 51– 81. doi : 10.1145/1388240.1388254 . ISSN 0163-5700 . S2CID 2298274 .  
  5. 1 2 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji (2008). Algoritmos holográficos por puertas de Fibonacci y reducciones holográficas para dureza . FOCS . Sociedad de Computación IEEE. págs. 644– 653. doi : 10.1109/FOCS.2008.34 . ISBN  978-0-7695-3436-7.
  6. ↑ Valiant, Leslie (2002). "Circuitos cuánticos que pueden simularse clásicamente en tiempo polinomial". SIAM Journal on Computing . 31 (4): 1229– 1254. doi : 10.1137/S0097539700377025 .
  7. ↑ Leslie G. Valiant (2006). Algoritmos accidentales [ Algoritmos accidentales ] . Fundamentos de la informática, Simposio anual del IEEE sobre. Sociedad de Computación del IEEE. págs. 509–517 . doi : 10.1109/FOCS.2006.7 . ISBN  0-7695-2720-5.