♯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?