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 :
Un problema de decisió de la classe NP acostuma a ser de la forma "hi ha una solució que satisfaci certa restricció?". Per exemple:
Els problemes corresponents dins de #P pregunten "quants?" enlloc de "si hi ha". Per exemple:
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.
This article uses material from the Wikipedia Català article ♯P, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). El contingut està disponible sota la llicència CC BY-SA 4.0 si no s'indica el contrari. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Català (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.