En la teoría de la complejidad computacional , la clase de complejidad #P (pronunciada "Sharp P" o, a veces, "number 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 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 funciones.. Los problemas representativos más difíciles de esta clase son #P-completos .
Un problema de decisión NP suele tener la forma "¿Existen soluciones que satisfagan ciertas restricciones?" Por ejemplo:
Claramente, 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 saber si hay alguna respuesta: simplemente cuéntelas y vea si el conteo es mayor que cero. Algunos de estos problemas, como la búsqueda de raíces , son lo suficientemente fáciles como para estar en FP , mientras que otros son #P-completos .
Una consecuencia del teorema de Toda es que una máquina del tiempo polinomial con un oráculo ( P #P ) puede resolver todos los problemas en PH , toda la jerarquía polinomial . De hecho, la máquina de tiempo polinomial solo necesita hacer una consulta #P para resolver cualquier problema en PH . Esta es una indicación de la extrema dificultad de resolver exactamente problemas #P -completos.
Sorprendentemente, algunos problemas #P que se consideran difíciles corresponden a problemas P fáciles (por ejemplo, de tiempo lineal) . Para obtener más información al respecto, 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 aceptan. Esto encuentra el bit más significativo en la respuesta del problema #P . En cambio, la clase de problema de decisión ⊕P (pronunciado "Parity-P") pide el bit menos significativo de la respuesta #P .