En la teoría de la complejidad computacional , la clase de complejidad #P (pronunciada "P aguda" o, a veces "número P" o "hash P") es el conjunto de problemas de conteo asociados con los problemas de decisión en el conjunto NP . Más formalmente, #P es la clase de problemas de función de la forma "calcular f ( x )", donde f es el número de caminos aceptables de una máquina de Turing no determinista que se ejecuta en tiempo polinomial . A diferencia de la mayoría de las clases de complejidad conocidas, no es una clase de problemas de decisión, sino una clase de problemas de función.. Los problemas representativos más difíciles de esta clase son # P-complete .
Relación con los problemas de decisión
Un problema de decisión NP suele tener la forma "¿Hay alguna solución que satisfaga determinadas limitaciones?" Por ejemplo:
- ¿Existe algún subconjunto de una lista de números enteros que sumen cero? ( problema de suma de subconjuntos )
- ¿Hay ciclos hamiltonianos en un gráfico dado con un costo inferior a 100? ( problema del viajante )
- ¿Hay asignaciones de variables que satisfagan una fórmula CNF (forma normal conjuntiva) dada ? ( Problema de satisfacibilidad booleano o SAT)
- ¿Tiene un polinomio real univariado alguna raíz positiva? ( Hallazgo de raíz )
Los problemas correspondientes de la función #P preguntan "cuántos" en lugar de "hay alguno". Por ejemplo:
- ¿Cuántos subconjuntos de una lista de números enteros suman cero?
- ¿Cuántos ciclos hamiltonianos en una gráfica dada han costado menos de 100?
- ¿Cuántas asignaciones de variables satisfacen una fórmula CNF dada?
- ¿Cuántas raíces de un polinomio real univariado son positivas?
¿Qué tan difícil es eso?
Claramente, un problema de #P debe ser al menos tan difícil como el correspondiente problema de NP . Si es fácil contar las respuestas, entonces debe ser fácil saber si hay algunas respuestas; simplemente cuéntelas y vea si el recuento es mayor que cero. Algunos de estos problemas, como la búsqueda de root , son lo suficientemente fáciles como para estar en FP , mientras que otros son # P-complete .
Una consecuencia del teorema de Toda es que una máquina de tiempo polinomial con un oráculo #P ( P #P ) puede resolver todos los problemas en PH , la jerarquía polinomial completa . De hecho, la máquina de tiempo polinomial solo necesita realizar una consulta #P para resolver cualquier problema en PH . Esta es una indicación de la extrema dificultad de resolver exactamente los problemas #P -completos.
Sorprendentemente, algunos problemas #P que se cree que son difíciles corresponden a problemas P fáciles (por ejemplo, de tiempo lineal) . Para obtener más información sobre esto, consulte # P-complete .
La clase de problema de decisión más cercana a #P es PP , que pregunta si la mayoría (más de la mitad) de las rutas de cálculo acepta. Esto encuentra el bit más significativo en la respuesta del problema #P . En cambio, la clase de problema de decisión pronounP (pronunciada "Paridad-P") pide el bit menos significativo de la respuesta #P .
Definiciones formales
#P se define formalmente de la siguiente manera:
- #P es el conjunto de todas las funciones tal que hay una máquina de Turing no determinista de tiempo polinomial tal que para todos , es igual al número de sucursales que aceptan en gráfico de cálculo de . [1]
#P también se puede definir de manera equivalente en términos de un verificador. Un problema de decisión está en NP si existe un certificado verificable en tiempo polinomial para una instancia de problema dada, es decir, NP pregunta si existe una prueba de pertenencia para la entrada que pueda verificarse para verificar su corrección en tiempo polinomial. La clase #P pregunta cuántos certificados existen para una instancia de problema cuya corrección se puede verificar en tiempo polinomial. [1] En este contexto, #P se define de la siguiente manera:
- #P es el conjunto de funciones tal que existe un polinomio y una máquina de Turing determinista en tiempo polinomial , llamado el verificador, de modo que para cada , . [2] (En otras palabras, es igual al tamaño del conjunto que contiene todos los certificados de tamaño polinomial).
Historia
La clase de complejidad #P fue definida por primera vez por Leslie Valiant en un artículo de 1979 sobre el cálculo del permanente de una matriz cuadrada , en el que demostró que permanente es # P-completo . [3]
Larry Stockmeyer ha demostrado que para cada problema de #Pexiste un algoritmo aleatorio que usa un oráculo para SAT, que dada una instancia de y devuelve con alta probabilidad un número tal que . [4] El tiempo de ejecución del algoritmo es polinomial en y . El algoritmo se basa en el lema hash sobrante .
Ver también
- Computación cuántica
Referencias
- ↑ a b Barak, Boaz (primavera de 2006). "Complejidad de contar" (PDF) . Ciencias de la Computación 522: Complejidad Computacional . Universidad de Princeton.
- ^ Arora, Sanjeev ; Barak, Boaz (2009). Complejidad computacional: un enfoque moderno . Prensa de la Universidad de Cambridge. pag. 344. ISBN 978-0-521-42426-4.
- ^ Leslie G. Valiant (1979). "La complejidad de cálculo de la permanente". Informática Teórica . Elsevier . 8 (2): 189-201. doi : 10.1016 / 0304-3975 (79) 90044-6 .
- ^ Stockmeyer, Larry (noviembre de 1985). "Sobre algoritmos de aproximación para #P" (PDF) . Revista SIAM de Computación . 14 (4): 849. doi : 10.1137 / 0214060 . Archivado desde el original (PDF) en 2009. Resumen de Lay .
enlaces externos
- Complejidad Zoo : Clase #P