Co-NP-complet

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie de la complexité, un problème est dit co-NP-complet s'il est co-NP et si tout problème co-NP est réductible en temps polynomial à lui. Autrement dit, c'est la classe des problèmes complets correspondant à co-NP. Tout problème co-NP-complet est le complémentaire d'un problème NP-complet.

Exemples[modifier | modifier le code]

Notes et références[modifier | modifier le code]