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:
- El problema está en #P , la clase de problemas que se pueden definir como contar el número de caminos aceptables de una máquina de Turing no determinista de tiempo polinomial .
- El problema es #P -hard, lo que significa que todos los demás problemas en #P tienen una reducción de Turing o una reducción de conteo de tiempo polinomial . Una reducción de conteo es un par de transformaciones de tiempo polinómico de las entradas del otro problema a las entradas del problema dado y de las salidas del problema dado a las salidas del otro problema, lo que permite que el otro problema se resuelva utilizando cualquier subrutina para el problema dado. problema. Una reducción de Turing es un algoritmo para el otro problema que hace un número polinomial de llamadas a una subrutina para el problema dado y, fuera de esas llamadas, usa 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.
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.
Ejemplos de
Ejemplos de problemas # P-complete incluyen:
- ¿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ántas coincidencias perfectas hay para un gráfico bipartito dado ?
- ¿Cuál es el valor del permanente de una matriz dada cuyas entradas son 0 o 1? (Ver # P-completitud de 01-permanente ).
- ¿Cuántas coloraciones de gráficos que usan k colores hay para un gráfico en particular G ?
- ¿Cuántas extensiones lineales diferentes existen para un determinado conjunto parcialmente ordenado o, de manera equivalente, cuántos ordenamientos topológicos diferentes existen para un gráfico acíclico dirigido dado ? [1]
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 .
Problemas sencillos con las versiones de conteo rígido
Algunos problemas # P-completos corresponden a problemas fáciles ( tiempo polinomial ). Determinar la satisfacibilidad de una fórmula booleana en DNF es fácil: tal 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 a diferencia de contar el número de clasificaciones topológicas. Se puede encontrar una sola coincidencia perfecta en tiempo polinomial, pero contar todas las coincidencias perfectas es # P-completo. El problema de conteo de correspondencia 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ó los problemas de clase #P y # P-completo por primera vez. [2]
Aproximación
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 de # 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. [3]
Referencias
- ^ Brightwell, Graham R .; Winkler, Peter (1991). "Contando extensiones lineales". Orden . 8 (3): 225–242. doi : 10.1007 / BF00383444 ..
- ^ Leslie G. Valiant (1979). "La complejidad de computar lo permanente" . Informática Teórica . Elsevier. 8 (2): 189-201. doi : 10.1016 / 0304-3975 (79) 90044-6 .
- ^ Mark R. Jerrum; Leslie G. Valiant; Vijay V. Vazirani (1986). "Generación aleatoria de estructuras combinatorias a partir de una distribución uniforme" . Informática Teórica . Elsevier. 43 : 169-188. doi : 10.1016 / 0304-3975 (86) 90174-x .
Otras lecturas
- Vazirani, Vijay V. (2003). Algoritmos de aproximación . Berlín: Springer. ISBN 3-540-65367-8.