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.
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:
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
Categoria:Classes de complexitat