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.

Sin embargo, existen algoritmos probabilísticos que dan una buena aproximación a algunos problemas #P-completos con una muy buena probabilidad. Esta es una de las mejores demostraciones del potencial de los algoritmos probabilísticos.

Resulta sorprendente que algunos problemas #P-completos corresponden a problemas en P. El segundo de los ejemplos dados anteriormente está en esta categoría. La pregunta "¿Existe una correspondencia perfecta para un grafo bipartito?" puede ser respondida en tiempo polinómico. Específicamente, para un grafo con V vértices y E aristas, la pregunta se puede responder en tiempo O(VE).