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ó és a #P si existeix un polinomi i una màquina de Turing determinista de temps polinòmic M tal que per tot :
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
Categoria:Classes de complexitat