♯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
[modifica]- ↑ V., Vazirani, Vijay. Approximation algorithms. Berlín: Springer, 2001. ISBN 3540653678.
- ↑ «The complexity of computing the permanent» (en anglès). Theoretical Computer Science, 8, 2, 01-01-1979, pàg. 189–201. DOI: 10.1016/0304-3975(79)90044-6. ISSN: 0304-3975.
| Considerades tractables | |
|---|---|
| Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
