♯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.^[1]

Més formalment, una funció ${\displaystyle f:\{0,1\}^{*}\rightarrow \mathbb {N} }$ és a #P si existeix un polinomi ${\displaystyle p:\mathbb {N} \rightarrow \mathbb {N} }$i una màquina de Turing determinista de temps polinòmic M tal que per tot ${\displaystyle x\in \{0,1\}^{*}}$:^[2]

${\displaystyle 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.^[3]

De forma sorprenent, alguns problemes de #P que es creu que són molt complicats es corresponen amb problemes de la classe P.^[4]

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.^[2]

També es coneix que si PSPACE = P, llavors #P = FP.

Referències