# ♯P

En teoria de la complexitat, la classe de complexitat #P (es pronuncia "nombre P" o "hash P") és el conjunt dels problemes de comptatge associats als problemes de decisió de la classe NP. Més formalment, #P és la classe de problemes funcionals de la forma "computa f(x)" on f és el nombre de camins que accepten d'una màquina de Turing no determinista en temps polinòmic. A diferència d'altres classes de complexitat, no és una classe de problemes de decisió si no de problemes de comptatge.
Més formalment, una funció $f:\{0,1\}^{*}\rightarrow \mathbb {N}$ és a #P si existeix un polinomi $p:\mathbb {N} \rightarrow \mathbb {N}$i una màquina de Turing determinista de temps polinòmic M tal que per tot $x\in \{0,1\}^{*}$:
   $f(x)=\mid \{y\in \{0,1\}^{p(|x|)}:M(x,y)=1\}\mid$

## Relació amb problema de decisió

Un problema de decisió de la classe NP acostuma a ser de la forma "hi ha una solució que satisfaci certa restricció?". Per exemple:
* Hi ha cap subconjunt d'una llista d'enters que sumats doni zero? (problema de la suma de subconjunts)
* Hi ha cap camí hamiltonià en un graf donat que costi menys de 100? (Problema del viatjant de comerç)
* Hi ha cap assignació de variables que satisfaci una fórmula donada en CNF? (Problema de satisfacibilitat booleana o SAT)
Els problemes corresponents dins de #P pregunten "quants?" enlloc de "si hi ha". Per exemple:
* Quants subconjunts d'enters sumen zero?
* Quants camins hamiltonians hi ha en graf donat que costin menys de 100?
* Quantes assignacions de variables hi ha que satisfacin una fórmula donada en CNF?

## Relació amb d'altres classes

Sembla clar que #P és almenys igual de costós que els problemes NP corresponents: si fos senzill contar les respostes, seria senzill saber si n'hi ha o no.
Una conseqüència del Teorema de Toda és una màquina amb temps polinòmic i oracle de #P (P$^{♯P}$) pot resoldre tots els problemes de la classe PH, tota la jerarquia polinòmica. De fet, la màquina de temps polinòmic només necessita preguntar per un sol problema de #P per resoldre qualsevol problema de PH. Això és un indicador de l'extrema dificultat de resoldre els problemes de #P-complet.
De forma sorprenent, alguns problemes de #P que es creu que són molt complicats es corresponen amb problemes de la classe P.
La classe de problemes de decisió més propera a #P és la classe PP, que pregunta per si la majoria de camins d'execució accepten. Això resol el bit més significatiu de la resposta d'un problema #P. Els problemes de ⊕P responen donant el bit menys significatiu dels mateixos problemes de PP.
Tampoc se sap si #P = FP (la classe anàloga a P per funcions amb més d'un bit de sortida). Se sap, però, que si #P = FP, llavors P = NP. No se sap si la implicació a la inversa també és vàlida, això és, que si P = NP llavors #P = FP.
També es coneix que si PSPACE = P, llavors #P = FP.

## Referències

* ↑ Valiant, L.G. «The complexity of computing the permanent». Theoretical Computer Science, 8, 2, 1979, pàg. 189–201. DOI: 10.1016/0304-3975(79)90044-6. ISSN: 0304-3975.
* 1 2 Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264.
* ↑ Toda, S. «On the computational power of PP and (+)P» (en anglès). 30th Annual Symposium on Foundations of Computer Science, 1989.. IEEE, 1989. DOI: 10.1109/sfcs.1989.63527.
* ↑ «Complexity Zoo:Symbols - Complexity Zoo» (en anglès). Arxivat de l'original el 2018-01-19. [Consulta: 4 desembre 2018].