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