Numeral-P-completo
En teoría de la complejidad computacional, la clase de complejidad \#P-completo (se pronuncia numeral-P-completo) es el conjunto de los problemas de conteo que pertenecen a \#P tales que todo problema de \#P se puede reducir en todos los de $P-completo en tiempo polinómico.
Algunos ejemplos de \#P-completo incluyen:
● ¿Cuantas asignaciones de variables satisfacen una fórmula dada?
● ¿Cuantas correspondencias perfectas hay en un grafo bipartito?
Se piensa que no hay algoritmos en tiempo polinómico para resolver problemas \#P-completos. Inclusive, no se conocen algoritmos deterministas que puedan dar una solución aproximada de calidad razonable.
Enciclopedia Universal.
2012.