Vés al contingut

♯P

De la Viquipèdia, l'enciclopèdia lliure

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

Relació amb problema de decisió

[modifica]

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:

  • 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

[modifica]

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

[modifica]
  1. 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.
  2. 2,0 2,1 Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264. 
  3. 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.
  4. «Complexity Zoo:Symbols - Complexity Zoo» (en anglès). Arxivat de l'original el 2018-01-19. [Consulta: 4 desembre 2018].