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]
  1. ↑ Handbook of theoretical computer science. 1st MIT Press pbk. ed. Amsterdam: Elsevier, 1994, ©1990. ISBN 0262720205. 
  2. ↑ «Complexity Zoo:C - Complexity Zoo» (en anglès). Arxivat de l'original el 2018-12-01. [Consulta: 1r desembre 2018].
  3. ↑ Pierre), Bovet, Daniel P. (Daniel. Introduction to the theory of complexity. Nova York: Prentice Hall, 1994. ISBN 0139153802.