Los problemas #P-completos (que se pronuncian "sharp P complete" o "number P complete") forman una clase de complejidad en la teoría de la complejidad computacional . Los problemas de esta clase de complejidad se definen por tener las dos propiedades siguientes:
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 de P versus NP al implicar que P y NP son iguales. No se conoce ningún algoritmo de ese tipo, ni tampoco se conoce una prueba de que no exista tal algoritmo.
Algunos ejemplos de problemas #P-completos incluyen:
Todos ellos son necesariamente miembros de la clase #P también. Como no-ejemplo, considere el caso de contar soluciones a un problema de 1-satisfacibilidad: una serie de variables que están restringidas individualmente, pero no tienen relaciones entre sí. Las soluciones se pueden contar de manera eficiente, multiplicando el número de opciones para cada variable de manera aislada. Por lo tanto, este problema está en #P , pero no puede ser #P-completo 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 satisfacible si y solo si contiene una conjunción satisfacible (una que no contenga una variable y su negación), mientras que contar el número de asignaciones satisfactorias es #P-completo. Además, decidir la 2-satisfacibilidad es fácil en comparación con contar el número de asignaciones satisfactorias. La ordenación topológica es fácil en contraste con contar el número de ordenaciones topológicas. Se puede encontrar una única coincidencia perfecta en tiempo polinomial, pero contar todas las coincidencias perfectas es #P-completo. El problema de conteo de coincidencia perfecta fue el primer problema de conteo 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ó la clase #P y los problemas #P-completos por primera vez. [3]
Existen 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 aleatorio de tiempo polinomial completo , o "FPRAS", que, informalmente, producirá con alta probabilidad una aproximación con un grado arbitrario de precisión, en un tiempo que es polinomial con respecto tanto al tamaño del problema como al 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 produzca consistentemente una aproximación de un problema #P-completo que esté dentro de una proporción polinomial en el tamaño de la entrada de la respuesta exacta, entonces ese algoritmo puede usarse para construir un FPRAS. [4]