♯P-complet

En teoria de la complexitat, la classe de complexitat #P-Complet (es pronuncia "nombre P complet" o "hash P complet") és la classe dels problemes de decisió tals que son a dins la classe #P i son #P-hard, és a dir, qualsevol altre problema a #P es pot reduir a aquests problemes.^[1]

Un algorisme de temps polinòmic que resolgui algun problema #P-complet resoldria el problema P = NP. No es coneix cap algorisme d'aquesta mena i se suposa que no n'existeix cap, tot i que no hi ha cap demostració.

Alguns exemples de problemes d'aquesta classe són els següents:^[2]

• Quantes assignacions diferents satisfan una fórmula booleana donada? (#SAT)
• Quantes assignacions diferents satisfan una fórmula en forma normal disjuntiva (DNF)?
• Quantes assignacions diferents satisfan un problema 2-SAT?
• Quants aparellaments hi ha per un graf bipartit donat?
• Quantes coloracions de grafs amb k colors es poden fer per un graf donat?

Referències