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.
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 dura 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 utilizar 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.
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 gráfico 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 grafo bipartito, el teorema de Valiant implica [9] que el problema de contar el número de emparejamientos perfectos en un grafo bipartito es # P-completo , y junto 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 se puede resolver 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]