- El teorema de Valiant afirma que calcular el permanente de una matriz es # P-Hard [1]. El artículo que presenta el teorema [2] también introdujo #P como una nueva clase de complejidad computacional. La nueva clase es útil para distinguir problemas para los cuales es fácil encontrar una solución, es decir, se puede hacer en tiempo polinómico, pero contar el número total de soluciones es difícil, es decir, no se puede hacer en tiempo polinómico.
- Se sabe que varios problemas son # P-Hard. El artículo de Valiant establece el cálculo del permanente como uno de esos problemas, que también es equivalente al problema de contar el número de coincidencias perfectas en un gráfico bipartito (se puede obtener una coincidencia perfecta utilizando el algoritmo Hopcroft-Karp).
- La primera vez que vi #P fue en el libro de texto de Probabilistic Graphical Models de Koller y Friedman. El concepto surgió naturalmente y se usó muchas veces para describir diferentes inferencias y problemas de aprendizaje en PGM.
- Un problema de decisión pregunta acerca de la existencia de una solución a un problema computacional y se responde proporcionando una solución o diciendo que no existe. Por otro lado, un problema de conteo pregunta por el número de soluciones para un problema computacional. Obviamente, el problema de contar es al menos tan difícil como el problema de decisión.
- Cuando el problema de decisión en sí es difícil, mientras que la verificación de la solución es fácil, el problema está en NP. Cuando es fácil encontrar una solución al problema de decisión, pero contar todas esas soluciones es difícil, el problema de contar está en #P mientras que el problema de decisión está en P: dos clases de complejidad muy diferentes.
- Si el problema de decisión es NP-Hard, el problema de conteo es al menos # P-Hard. Lo contrario no es cierto.
[1] Teorema de Valiant en Wikipedia: permanente es nítido-P-completo
[2] Leslie Valiant. La complejidad de cálculo de la permanente.
