Co-NP-complet
En teoria de la complexitat, la classe de complexitat co-NP-complet és el conjunt dels problemes de decisió més difícils de la classe co-NP, en el sentit que són els que menys s'assemblen als de la classe P. Un problema C pertany a co-NP-complet si està a co-NP i tot problema de co-NP té una transformació polinòmica cap C.[1][2]
Tot problema a co-NP-complet és el complementari d'un problema NP-complet. Hi ha problemes que poden estar alhora a NP i a co-NP, com tots els problemes dins la classe P o el problema de la factorització de nombres enters. Es desconeix si aquests dos conjunts son iguals, tot i que se sospita que no.[3]
Un exemple senzill de problema dins d'aquesta classe és el problema de la tautologia: determinar si una fórmula booleana és una tautologia.
Referències
[modifica]- ↑ Handbook of theoretical computer science. 1st MIT Press pbk. ed. Amsterdam: Elsevier, 1994, ©1990. ISBN 0262720205.
- ↑ «Complexity Zoo:C - Complexity Zoo» (en anglès). Arxivat de l'original el 2018-12-01. [Consulta: 1r desembre 2018].
- ↑ Pierre), Bovet, Daniel P. (Daniel. Introduction to the theory of complexity. Nova York: Prentice Hall, 1994. ISBN 0139153802.
| 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 | |
