♯P-completo

Los problemas #P-completos (pronunciados "sharp P complete", "number P complete" o "hash 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:

• El problema está en #P , la clase de problemas que se pueden definir como contar el número de caminos de aceptación de una máquina de Turing no determinista de tiempo polinomial .

• El problema es #P -difícil, lo que significa que cualquier otro problema en #P tiene una reducción de Turing o una reducción de conteo en tiempo polinomial . Una reducción de conteo es un par de transformaciones en tiempo polinomial desde las entradas del otro problema a las entradas del problema dado y desde las salidas del problema dado a las salidas del otro problema, lo que permite resolver el otro problema utilizando cualquier subrutina para el problema dado. Una reducción de Turing en tiempo polinomial es un algoritmo para el otro problema que realiza un número polinomial de llamadas a una subrutina para el problema dado y, fuera de esas llamadas, utiliza tiempo polinomial. En algunos casos, se utilizan reducciones parsimoniosas , un tipo de reducción más específico que conserva el número exacto de soluciones.

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 ningún algoritmo de este tipo, ni tampoco se conoce ninguna prueba de que no exista.

Algunos ejemplos de problemas #P-completos son:

• ¿Cuántas asignaciones de variables diferentes satisfarán una fórmula booleana general dada? ( #SAT )
• ¿Cuántas asignaciones de variables diferentes satisfarán una fórmula DNF dada?
• ¿Cuántas asignaciones de variables diferentes satisfarán un problema de 2-satisfacibilidad dado?
• ¿Cuántos emparejamientos perfectos existen para un grafo bipartito dado ?
• ¿Cuál es el valor del permanente de una matriz dada cuyas entradas son 0 o 1? (Véase #P-completitud del permanente 01 ).
• ¿Cuántas coloraciones de grafos que utilizan k colores existen para un grafo G en particular ?
• ¿Cuántas extensiones lineales diferentes existen para un conjunto parcialmente ordenado dado , o, equivalentemente, cuántos ordenamientos topológicos diferentes existen para un grafo dirigido acíclico dado ? ^{[ 2 ]}

Todos estos son necesariamente miembros de la clase #P también. Como contraejemplo, consideremos el caso de contar soluciones a un problema de 1-satisfacibilidad : una serie de variables que están restringidas individualmente, pero no tienen relación entre sí. Las soluciones se pueden contar eficientemente, 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-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 ( de tiempo polinomial ). Determinar la satisfacibilidad de una fórmula booleana en forma normal disyuntiva es fácil: dicha fórmula es satisfacible si y solo si contiene una conjunción satisfacible (una que no contiene una variable y su negación), mientras que contar el número de asignaciones que la satisfacen es #P-completo. Además, decidir la 2-satisfacibilidad es fácil en comparación con contar el número de asignaciones que la satisfacen. La ordenación topológica es fácil en contraste con contar el número de ordenaciones topológicas. Se puede encontrar un único emparejamiento perfecto en tiempo polinomial, pero contar todos los emparejamientos perfectos es #P-completo. El problema de contar emparejamientos perfectos fue el primer problema de conteo correspondiente a un problema de decisión 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 proporcionan 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 aleatoria totalmente polinomial , o "FPRAS", que, informalmente, producirá con alta probabilidad una aproximación con un grado de precisión arbitrario, en un tiempo polinomial con respecto al tamaño del problema y al grado de precisión requerido. Jerrum , Valiant y Vazirani demostraron que todo problema #P-completo tiene un FPRAS o es esencialmente imposible de aproximar; si existe algún algoritmo de tiempo polinomial que produzca 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 ]}

• Vazirani, Vijay V. (2003). Algoritmos de aproximación . Berlín: Springer. ISBN 3-540-65367-8.