La # P-completitud de 01-permanente , a veces conocida como teorema de Valiant , [1] es una prueba matemática sobre la permanente de las matrices , considerada un resultado fundamental en la teoría de la complejidad computacional . [2] [3] En un artículo académico de 1979 , Leslie Valiant demostró que el problema computacional de calcular la permanente de una matriz es # P-difícil , incluso si la matriz está restringida para tener entradas que sean todas 0 o 1. [4 ] En este caso restringido, calcular el permanente es incluso# P-completo , porque corresponde al problema #P de contar el número de matrices de permutación que se pueden obtener al convertir unas en ceros.
El artículo de Valiant de 1979 también introdujo #P como una clase de complejidad . [5]
La definición de completitud de Valiant, y su prueba de completitud de 01-permanente, utilizaron reducciones de Turing en tiempo polinomial . En este tipo de reducción, una sola instancia difícil de algún otro problema en #P se reduce a calcular el permanente de una secuencia de múltiples gráficos, cada uno de los cuales podría depender potencialmente de los resultados de cálculos permanentes previos. Una simplificación posterior de Ben-Dor y Halevi (1993) mostró que es posible usar una noción más débil de reducción, una reducción por conteo de tiempo polinomial , que traduce el otro problema en una sola instancia del problema permanente.
Significado
Una razón para el interés en la complejidad computacional de lo permanente es que proporciona un ejemplo de un problema en el que la construcción de una única solución se puede hacer de manera eficiente pero donde contar todas las soluciones es difícil. [6] Como escribe Papadimitriou en su libro Computational Complexity :
Los problemas # P-complete más impresionantes e interesantes son aquellos para los que el problema de búsqueda correspondiente se puede resolver en tiempo polinomial. El problema PERMANENTE para matrices 0-1, que es equivalente al problema de contar coincidencias perfectas en un gráfico [...] bipartito, es el ejemplo clásico aquí. [1]
Específicamente, calcular el permanente (que se muestra difícil según los resultados de Valiant) está estrechamente relacionado con encontrar una coincidencia perfecta en un gráfico bipartito , que se puede resolver en tiempo polinomial mediante el algoritmo Hopcroft-Karp . [7] [8] Para un grafo bipartito con 2n vértices divididos en dos partes con n vértices cada una, el número de emparejamientos perfectos es igual al permanente de su matriz de biadjacencia y el cuadrado del número de emparejamientos perfectos es igual al permanente de su matriz de adyacencia . [9] Dado que cualquier matriz 0-1 es la matriz de biadjacencia de algún gráfico bipartito, el teorema de Valiant implica [9] que el problema de contar el número de emparejamientos perfectos en un gráfico bipartito es # P-completo , y en conjunto con el teorema de Toda esto implica que es difícil para toda la jerarquía polinomial . [10] [11]
La complejidad computacional de lo permanente también tiene cierta importancia en otros aspectos de la teoría de la complejidad: no se sabe si NC es igual a P (informalmente, si cada problema polinomialmente resuelto puede resolverse mediante un algoritmo paralelo de tiempo polilogarítmico ) y Ketan Mulmuley ha sugerido un enfoque para resolver esta cuestión que se basa en escribir lo permanente como determinante de una matriz. [12]
Hartmann [13] demostró una generalización del teorema de Valiant sobre la complejidad de calcular inmanentes de matrices que generalizan tanto el determinante como el permanente.
Prueba de Ben-Dor y Halevi
A continuación, se describe la prueba de que calcular el permanente de una matriz 01 es # P-completo . Sigue principalmente la demostración de Ben-Dor y Halevi (1993) . [14]
Descripción general
Cualquier matriz cuadrada puede verse como la matriz de adyacencia de un gráfico dirigido, conque representa el peso de la arista desde el vértice i al vértice j . Entonces, el permanente de A es igual a la suma de los pesos de todos los ciclos de cobertura del gráfico; esta es una interpretación teórica de grafos de lo permanente .
#SAT , un problema de función relacionado con el problema de satisfacibilidad booleano , es el problema de contar el número de asignaciones satisfactorias de una fórmula booleana dada. Es un problema # P-completo (por definición), ya que cualquier máquina NP puede codificarse en una fórmula booleana mediante un proceso similar al del teorema de Cook , de modo que el número de asignaciones satisfactorias de la fórmula booleana es igual al número de aceptar caminos de la máquina NP. Cualquier fórmula en SAT se puede reescribir como una fórmula en forma 3- CNF preservando el número de asignaciones satisfactorias, por lo que #SAT y # 3SAT son equivalentes y # 3SAT es # P-complete también.
Para demostrar que 01-Permanent es # P-hard , es suficiente demostrar que el número de asignaciones satisfactorias para una fórmula 3-CNF puede expresarse sucintamente como una función del permanente de una matriz que contiene solo los valores 0 y 1. Esto generalmente se logra en dos pasos:
- Dada una fórmula de 3-CNF φ, construya una gráfica ponderada entera dirigida , de manera que la suma de los pesos del ciclo cubre de (o de manera equivalente, el permanente de su matriz de adyacencia) es igual al número de asignaciones satisfactorias de φ. Esto establece que Permanente es # P-duro.
- A través de una serie de reducciones, reduzca Permanente a 01-Permanente, el problema de calcular el permanente de una matriz todas las entradas 0 o 1. Esto establece que 01-permanente es # P-duro también.
Construyendo el gráfico de números enteros
Dada una fórmula 3CNF con m cláusulas yn variables, se puede construir una gráfica dirigida y ponderada tal que
- cada asignación satisfactoria para tendrá un conjunto correspondiente de cubiertas de ciclo en donde la suma de los pesos de las cubiertas de ciclo en este conjunto será ; y
- todas las demás cubiertas de ciclo en tendrá pesos que suman 0.
Así que si es el número de asignaciones satisfactorias para , el permanente de este gráfico será . (La prueba original de Valiant construye una gráfica con entradas en cuyo permanente es dónde es "el doble de apariciones de literales en "- .)
La construcción del gráfico utiliza un componente que se trata como una "caja negra". Para mantener la explicación simple, las propiedades de este componente se dan sin definir realmente la estructura del componente.
Para especificar G φ , primero se construye un nodo variable en G φ para cada una de las n variables en φ . Además, para cada una de las cláusulas m en φ , se construye un componente de cláusula C j en G φ que funciona como una especie de "caja negra". Todo lo que debe tenerse en cuenta sobre C j es que tiene tres bordes de entrada y tres bordes de salida. Los bordes de entrada provienen de nodos variables o de componentes de cláusulas anteriores (p. Ej., C o para algunos o < j ) y los bordes de salida van a nodos variables oa componentes de cláusulas posteriores (p. Ej., C o para algunos). Los primeros bordes de entrada y salida se corresponden con la primera variable de la cláusula j , y así sucesivamente. Hasta el momento, se han especificado todos los nodos que aparecerán en el gráfico G φ .
A continuación, se considerarían los bordes. Para cada variable de , uno hace un ciclo verdadero (ciclo T) y un ciclo falso (ciclo F) en . Para crear el ciclo T, uno comienza en el nodo variable para y dibuja un borde en el componente de cláusula que corresponde a la primera cláusula en la que aparece. Si es la primera variable en la cláusula de correspondiente a , este borde será el primer borde de entrada de , y así. De ahí, dibuje un borde al siguiente componente de la cláusula correspondiente a la siguiente cláusula de en el cual aparece, conectándolo desde el borde de salida apropiado de al borde de entrada apropiado del siguiente componente de cláusula, y así sucesivamente. Después de la última cláusula en la que aparece, conectamos el borde de salida apropiado del componente de cláusula correspondiente de nuevo a nodo variable. Por supuesto, esto completa el ciclo. Para crear el ciclo F, se seguiría el mismo procedimiento, pero conéctesenodo variable a los componentes de la cláusula en los que ~ aparece, y finalmente de vuelta a nodo variable. Todos estos bordes fuera de los componentes de la cláusula se denominan bordes externos , todos los cuales tienen un peso 1. Dentro de los componentes de la cláusula, los bordes se denominan bordes internos . Cada borde externo es parte de un ciclo T o un ciclo F (pero no ambos, eso forzaría la inconsistencia).
Tenga en cuenta que el gráfico es de tamaño lineal en , por lo que la construcción se puede realizar en polytime (suponiendo que los componentes de la cláusula no causen problemas).
Propiedades notables del gráfico
Una propiedad útil de es que sus coberturas de ciclo corresponden a asignaciones de variables para . Para una cubierta de ciclo Z de, se puede decir que Z induce una asignación de valores para las variables enen caso de que Z contenga todos los bordes externos enciclo T y ninguno de los bordes externos en Ciclo F para todas las variables que la asignación hace verdadera, y viceversa para todas las variables que la asignación hace falsa. Aunque cualquier cobertura de ciclo dada Z no necesita inducir una asignación para, Cualquiera que hace induce exactamente una asignación, y la misma asignación inducida depende sólo de los bordes externos de Z . El término Z se considera una cobertura de ciclo incompleta en esta etapa, porque se habla solo de sus bordes externos, M. En la sección siguiente, se consideran M-terminaciones para mostrar que uno tiene un conjunto de cubiertas de ciclo correspondientes a cada M que tiene las propiedades necesarias.
El tipo de Z que no induce asignaciones son los que tienen ciclos que "saltan" dentro de los componentes de la cláusula. Es decir, si por cada, al menos uno de Los bordes de entrada están en Z , y cada borde de salida de los componentes de la cláusula está en Z cuando el borde de entrada correspondiente está en Z , entonces Z es apropiado con respecto a cada componente de la cláusula, y Z producirá una asignación satisfactoria para. Esto se debe a que las Z adecuadas contienen el ciclo T completo o el ciclo F completo de cada variable. en así como cada uno de los bordes que entran y salen de cada componente de la cláusula. Por lo tanto, estas Z asignan verdadero o falso (pero nunca ambos) a caday asegúrese de que se cumpla cada cláusula. Además, los conjuntos de cubiertas de ciclo correspondientes a todas esas Z tienen peso, y cualquier otra Z tiene peso. Las razones de esto dependen de la construcción de los componentes de la cláusula y se describen a continuación.
El componente de la cláusula
Comprender las propiedades relevantes de los componentes de la cláusula , uno necesita la noción de una M-terminación. Una cubierta de ciclo Z induce una asignación satisfactoria en caso de que sus bordes externos satisfagan ciertas propiedades. Para cualquier cubierta de ciclo de, considere solo sus bordes externos, el subconjunto M. Sea M un conjunto de bordes externos. Un conjunto de bordes internos L es una terminación M por si acaso es una portada de ciclo de . Además, denote el conjunto de todas las M completaciones por y el conjunto de todas las cubiertas de ciclo resultantes de por .
Recuerde que la construcción de era tal que cada borde externo tenía un peso 1, por lo que el peso de , las cubiertas de ciclo resultantes de cualquier M, depende solo de los bordes internos involucrados. Agregamos aquí la premisa de que la construcción de los componentes de la cláusula es tal que la suma sobre posibles M-completaciones del peso de los bordes internos en cada componente de la cláusula, donde M es propia en relación con el componente de la cláusula, es 12. De lo contrario, el peso de los bordes internos es 0. Dado que hay m componentes de cláusula, y la selección de conjuntos de bordes internos, L, dentro de cada componente de cláusula es independiente de la selección de conjuntos de bordes internos en otros componentes de cláusula, por lo que se puede multiplicar todo para conseguir el peso de. Entonces, el peso de cada, donde M induce una asignación satisfactoria, es . Además, donde M no induce una asignación satisfactoria, M no es apropiado con respecto a algunos, por lo que el producto de los pesos de los bordes internos en estarán .
El componente de la cláusula es un gráfico dirigido y ponderado con 7 nodos con bordes ponderados y nodos dispuestos para producir las propiedades especificadas anteriormente, y se da en el Apéndice A de Ben-Dor y Halevi (1993). Tenga en cuenta que los bordes internos aquí tienen pesos extraídos del conjunto; no todas las aristas tienen pesos de 0 a 1.
Finalmente, dado que la suma de pesos de todos los conjuntos de cubiertas de ciclo que inducen cualquier asignación satisfactoria en particular es 12 m , y la suma de pesos de todos los demás conjuntos de cubiertas de ciclo es 0, uno tiene Perm ( G φ ) = 12 m · ( # φ ). La siguiente sección reduce el cálculo de Perm () al permanente de una matriz 01.
01-Matriz
La sección anterior ha demostrado que Permanente es # P-difícil. A través de una serie de reducciones, cualquier permanente se puede reducir al permanente de una matriz con entradas solo 0 o 1. Esto demostrará que 01-Permanent es # P-hard también.
Reducción a una matriz no negativa
Usando aritmética modular , convierta una matriz entera A en una matriz equivalente no negativa para que el permanente de se puede calcular fácilmente a partir de la permanente de , como sigue:
Dejar frijol matriz entera donde ninguna entrada tiene una magnitud mayor que .
- Calcular . La elección de Q se debe al hecho de que
- Calcular
- Calcular
- Si entonces Perm ( A ) = P . De lo contrario
La transformación de dentro es polinomio en y , ya que el número de bits necesarios para representar es polinomio en y
A continuación se muestra un ejemplo de la transformación y por qué funciona.
Aquí, , , y , entonces . Por lo tanto
Observe cómo los elementos no son negativos debido a la aritmética modular. Es simple calcular el permanente
entonces . Luego, entonces
Reducción a potencias de 2
Tenga en cuenta que cualquier número se puede descomponer en una suma de potencias de 2 . Por ejemplo,
Este hecho se utiliza para convertir una matriz no negativa en una matriz equivalente cuyas entradas son todas potencias de 2. La reducción se puede expresar en términos de gráficos equivalentes a las matrices.
Dejar ser un -Gráfico dirigido ponderado de nodo con ponderaciones no negativas, donde la ponderación más grande es . Cada borde con peso se convierte en una arista equivalente con pesos en potencias de 2 de la siguiente manera:
- ,
Esto se puede ver gráficamente en la Figura 1. El subgráfico que reemplaza el borde existente contiene nodos y bordes.
Para demostrar que esto produce una gráfica equivalente que tiene el mismo permanente que el original, se debe mostrar la correspondencia entre las cubiertas del ciclo de y .
Considere alguna cubierta de ciclo en .
- Si una ventaja no está dentro , luego, para cubrir todos los nodos en el nuevo subgrafo, se deben usar los bucles automáticos. Dado que todos los bucles automáticos tienen un peso de 1, el peso de las cubiertas de ciclo en y partido.
- Si es en , luego en todas las cubiertas de ciclo correspondientes en , debe haber un camino desde a , donde u y v son los nodos del borde e . De la construcción, se puede ver que hay diferentes caminos y suma de todos estos caminos igual al peso del borde en el gráfico original . Entonces, el peso de las cubiertas de ciclo correspondientes en y partido.
Tenga en cuenta que el tamaño de es polinomio en y .
Reducción a 0-1
El objetivo aquí es reducir una matriz cuyas entradas son potencias de 2 en una matriz equivalente que contiene solo ceros y unos (es decir, un gráfico dirigido donde cada borde tiene un peso de 1).
Sea G un -Gráfico dirigido por nodos donde todos los pesos en los bordes son potencias de dos. Construye una gráfica,, donde el peso de cada borde es 1 y Perm (G) = Perm (G '). El tamaño de este nuevo gráfico, G ', es polinomio en y donde el peso máximo de cualquier borde en el gráfico G es .
Esta reducción se realiza localmente en cada borde en G que tiene un peso mayor que 1. Sea ser una ventaja en G con un peso . Se reemplaza por un subgrafo que se compone de nodos y bordes como se ve en la Figura 2. Cada borde en tiene un peso de 1. Por lo tanto, el gráfico resultante G 'contiene solo aristas con un peso de 1.
Considere alguna cubierta de ciclo en .
- Si un borde original del gráfico G no está en , no se puede crear una ruta a través del nuevo subgrafo . La única forma de formar una cubierta de ciclo sobreen tal caso, es que cada nodo del subgrafo realice su ciclo propio. Como cada borde tiene un peso de uno, el peso de la cubierta del ciclo resultante es igual al de la cubierta del ciclo original.
- Sin embargo, si el borde en G es parte de la cubierta del ciclo, entonces en cualquier cubierta del ciclo de debe haber un camino desde a en el subgrafo. En cada paso hacia abajo del subgrafo, hay dos opciones que uno puede hacer para formar ese camino. Uno debe tomar esta decisión veces, resultando en posibles caminos desde a . Por lo tanto, hay posibles cubiertas de ciclo y dado que cada trayecto tiene un peso de 1, la suma de los pesos de todas estas cubiertas de ciclo es igual al peso de la cubierta de ciclo original.
Prueba de Aaronson
En 2011, el científico de la computación cuántica Scott Aaronson demostró que lo permanente es # P-hard utilizando métodos cuánticos. [15]
Referencias
- ↑ a b Christos H. Papadimitriou . Complejidad computacional. Addison-Wesley , 1994. ISBN 0-201-53082-1 . Página 443
- ^ Allen Kent , James G. Williams, Rosalind Kent y Carolyn M. Hall (editores). Enciclopedia de microordenadores . Marcel Dekker , 1999. ISBN 978-0-8247-2722-2 ; pag. 34
- ^ Jin-Yi Cai, A. Pavan y D. Sivakumar, Sobre la dureza de lo permanente. En: STACS, '99: 16º Simposio anual sobre aspectos teóricos de la informática, Trier, Alemania, 4 al 6 de marzo de 1999 Actas. págs. 90–99. Springer-Verlag , Nueva York, LLC Pub. Fecha: Octubre de 2007. ISBN 978-3-540-65691-3 ; pag. 90.
- ^ Leslie G. Valiant (1979). "La complejidad de cálculo de la permanente". Informática Teórica . Elsevier. 8 (2): 189-201. doi : 10.1016 / 0304-3975 (79) 90044-6 .
- ^ Lance Fortnow . Mis diez teoremas de complejidad favoritos de la última década. Fundamentos de la tecnología del software y la informática teórica: Actas de la 14ª Conferencia, Madrás, India, 15 al 17 de diciembre de 1994. PS Thiagarajan (editor), págs. 256–275, Springer-Verlag , Nueva York, 2007. ISBN 978-3-540-58715-6 ; pag. 265
- ^ Bürgisser, Peter (2000). Completitud y reducción en la teoría de la complejidad algebraica . Algoritmos y Computación en Matemáticas. 7 . Berlín: Springer-Verlag . pag. 2. ISBN 978-3-540-66752-0. Zbl 0948.68082 .
- ^ John E. Hopcroft , Richard M. Karp : UnaAlgoritmo para coincidencias máximas en gráficos bipartitos. SIAM J. Comput. 2 (4), 225–231 (1973)
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "26.5: El algoritmo de etiquetado al frente". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 696–697. ISBN 0-262-03293-7.
- ^ a b Dexter Kozen . El diseño y análisis de algoritmos. Springer-Verlag , Nueva York, 1991. ISBN 978-0-387-97687-7 ; págs. 141-142
- ^ Seinosuke Toda . PP es tan difícil como la jerarquía de tiempo polinomial. SIAM Journal on Computing , Volumen 20 (1991), Número 5, págs. 865–877.
- ^ "Premio Gödel 1998. Seinosuke Toda" . Archivado desde el original el 8 de enero de 2014 . Consultado el 6 de julio de 2016 .
- ^ Ketan Mulmuley . Límites inferiores en un modelo paralelo sin operaciones de bits. SIAM Journal on Computing , Volumen 28 (1999), Número 4, págs. 1460–1509.
- ^ W. Hartmann. Sobre la complejidad de los inmanentes. Álgebra lineal y multilineal 18 (1985), no. 2, págs. 127–140.
- ^ Ben-Dor, Amir; Halevi, Shai (1993). "Zero-one permanente es #P -complete, una prueba más simple". Actas del 2do Simposio de Israel sobre Teoría y Sistemas de Computación (PDF) . págs. 108-117.
- ^ S. Aaronson , Una prueba óptica lineal de que lo permanente es # P-Hard