♯P

En la teoría de la complejidad computacional , la clase de complejidad #P (pronunciada "P fuerte" o, a veces, "P numérica" ​​o "P hash") 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 de aceptación 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 más difíciles y representativos de esta clase son #P-completos .

Un problema de decisión NP a menudo se puede plantear de la forma "¿Existen soluciones que satisfagan ciertas restricciones?" Por ejemplo:

• ¿Existen subconjuntos de una lista de números enteros cuya suma sea cero? ( problema de suma de subconjuntos )
• ¿Existen ciclos hamiltonianos en un grafo dado con un coste inferior a 100? ( problema del viajante )
• ¿Existen asignaciones de variables que satisfagan una fórmula dada en forma normal conjuntiva (FNC) ? ( Problema de satisfacibilidad booleana o SAT)
• ¿Tiene un polinomio real univariado alguna raíz positiva? ( búsqueda de raíces )

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 un gráfico dado han costado menos de 100?
• ¿Cuántas asignaciones de variables satisfacen una fórmula CNF dada?
• ¿Cuántas raíces positivas tienen un polinomio real univariado?

Es evidente que un problema #P debe ser al menos tan difícil como el problema NP correspondiente . Si es fácil contar las respuestas, entonces debe ser fácil determinar si existen: basta con contarlas y comprobar si el recuento es mayor que cero. Algunos de estos problemas, como el conteo de raíces , son lo suficientemente fáciles como para pertenecer a FP , mientras que otros son #P-completos .

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 , toda la jerarquía polinomial . De hecho, la máquina de tiempo polinomial solo necesita realizar una consulta #P para resolver cualquier problema en PH . Esto indica la extrema dificultad de resolver problemas #P -completos de forma exacta.

Sorprendentemente, algunos problemas #P que se consideran difíciles corresponden a problemas P fáciles (por ejemplo, de tiempo lineal) . Para más información sobre esto, consulte #P-completo .

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 aceptan. Esto encuentra el bit más significativo en la respuesta del problema #P . La clase de problema de decisión ⊕P (pronunciado "Paridad-P"), en cambio, pregunta por el bit menos significativo de la respuesta de #P .

#P se define formalmente de la siguiente manera:

#P es el conjunto de todas las funciones${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$de tal manera que exista una máquina de Turing no determinista de tiempo polinomial.${\displaystyle M}$de tal manera que para todos${\displaystyle x\in \{0,1\}^{*}}$,${\displaystyle f(x)}$es igual al número de sucursales que aceptan${\displaystyle M}$gráfico de cálculo de${\displaystyle x}$. ^{[ 1 ]}

#P también puede definirse de forma equivalente en términos de un verificador. Un problema de decisión pertenece a 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 en tiempo polinomial. Las preguntas en #P preguntan cuántos certificados existen para una instancia de problema que puedan verificarse en tiempo polinomial. ^{[ 1 ]} En este contexto, #P se define de la siguiente manera:

#P es el conjunto de funciones${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$tal que existe un polinomio${\displaystyle p:\mathbb {N} \to \mathbb {N} }$y una máquina de Turing determinista de tiempo polinomial${\displaystyle V}$, llamado el verificador, de tal manera que para cada${\displaystyle x\in \{0,1\}^{*}}$,${\displaystyle f(x)={\Big |}{\big \{}y\in \{0,1\}^{p(|x|)}:V(x,y)=1{\big \}}{\Big |}}$. ^{[ 2 ]} (En otras palabras,${\displaystyle f(x)}$es igual al tamaño del conjunto que contiene todos los certificados de tamaño polinomial).

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 el permanente es #P-completo . ^{[ 3 ]}

Larry Stockmeyer ha demostrado que para cada problema #P${\displaystyle P}$Existe un algoritmo aleatorio que utiliza un oráculo para SAT, que dada una instancia${\displaystyle a}$de${\displaystyle P}$y${\displaystyle \epsilon >0}$devuelve con alta probabilidad un número${\displaystyle x}$de tal manera que${\displaystyle (1-\epsilon )P(a)\leq x\leq (1+\epsilon )P(a)}$. ^{[ 4 ]} El tiempo de ejecución del algoritmo es polinomial en${\displaystyle a}$y${\displaystyle 1/\epsilon }$El algoritmo se basa en el lema hash restante .

• Computación cuántica#Relación con la teoría de la computabilidad y la complejidad – Tecnología de hardware informático que utiliza la mecánica cuántica 

• Zoológico de la complejidad : Clase #P