Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Co-NP
Résumé
En informatique théorique, co-NP (ou coNP) est une classe de complexité, c'est-à-dire un ensemble de problèmes de décision au sens de la théorie de la complexité. C'est la classe complémentaire (au sens de la complexité) de la classe NP.
On donne deux définitions équivalentes.
co-NP est l'ensemble des langages qui ont pour complémentaire (au sens des langages) un langage de NP.
Une autre façon de voir est que co-NP est l'ensemble des langages pour lesquels une preuve vérifiable en temps polynomial peut prouver la non-appartenance du mot au langage (des contre-exemples).
On peut définir la classe coNP en utilisant des certificats.
Sur un alphabet , un langage est dans co-NP, s'il existe un polynôme et une machine de Turing en temps polynomial , tels que pour un mot , on a équivalence entre et le fait que pour tout certificat , la machine accepte l'entrée .
Comme pour la classe NP, on définit la notion de problèmes co-NP-difficile. Un problème est co-NP-difficile si tout problème co-NP s'y réduit en temps polynomial. Un problème est co-NP-complet s'il est dans co-NP et il est co-NP-difficile.
De tout problème dans NP, on peut construire un problème « dual » dans co-NP.
La question co-NP = NP est une question ouverte mais il est conjecturé que ces classes sont différentes. Si P = NP, alors NP = co-NP mais la réciproque n'est pas connue.
On sait que , mais l'égalité est une question ouverte. Le problème du test de primalité est connu pour être dans NP et co-NP, mais on pensait généralement qu'il n'était pas dans P ; jusqu'à ce qu'en 2002 on démontre qu'il est dans P (Théorème AKS).
Dans la hiérarchie polynomiale, co-NP correspond au premier étage existentiel : co-NP = .
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.
Maths Adulte La Rochelle université : Le résultat qui
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.