Los problemas # P-completo (pronunciado "P completo completo" o "número P completo") forman una clase de complejidad en la teoría de la complejidad computacional . Los problemas en esta clase de complejidad se definen teniendo las siguientes dos propiedades:
# Los problemas P-completos son al menos tan difíciles como los problemas NP-completos . [1] Un algoritmo de tiempo polinomial para resolver un problema # P-completo, si existiera, resolvería el problema P versus NP al implicar que P y NP son iguales. No se conoce tal algoritmo, ni se conoce una prueba de que tal algoritmo no exista.
Todos estos son necesariamente miembros de la clase #P también. Como no ejemplo, considere el caso de contar soluciones a un problema de satisfacibilidad 1 : una serie de variables que están restringidas individualmente, pero que no tienen relaciones entre sí. Las soluciones se pueden contar de manera eficiente, multiplicando el número de opciones para cada variable de forma aislada. Por lo tanto, este problema está en #P , pero no puede ser # P-complete a menos que #P = FP . Esto sería sorprendente, ya que implicaría que P = NP = PH .
Algunos problemas # P-completos corresponden a problemas fáciles ( tiempo polinomial ). Determinar la satisfacibilidad de una fórmula booleana en DNF es fácil: dicha fórmula es satisfactoria si y solo si contiene una conjunción satisfactoria (una que no contiene una variable y su negación), mientras que contar el número de asignaciones satisfactorias es # P- completo. Además, decidir la satisfacción 2 es fácil en comparación con contar el número de asignaciones satisfactorias. La clasificación topológica es fácil en contraste con contar el número de clasificaciones topológicas. Una única combinación perfectase puede encontrar en tiempo polinomial, pero contar todas las coincidencias perfectas es # P-completo. El problema de recuento de correspondencia perfecta fue el primer problema de recuento correspondiente a un problema P fácil que se demostró que era # P-completo, en un artículo de 1979 de Leslie Valiant que también definió los problemas de clase #P y # P-completo por primera vez. [3]
Hay algoritmos probabilísticos que devuelven buenas aproximaciones a algunos problemas # P-completos con alta probabilidad. Esta es una de las demostraciones del poder de los algoritmos probabilísticos.
Muchos problemas # P-completos tienen un esquema de aproximación aleatorizado en tiempo polinomial completo , o "FPRAS", que, informalmente, producirá con alta probabilidad una aproximación a un grado arbitrario de precisión, en el tiempo que es polinomial con respecto al tamaño del problema y el grado de precisión requerido. Jerrum , Valiant y Vazirani demostraron que cada problema # P-completo tiene un FPRAS o es esencialmente imposible de aproximar; Si hay algún algoritmo de tiempo polinomial que produce consistentemente una aproximación de un problema # P-completo que está dentro de una razón polinomial en el tamaño de la entrada de la respuesta exacta, entonces ese algoritmo puede usarse para construir un FPRAS. [4]