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. Définitions On donne deux définitions équivalentes. À partir de NP 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). Par certificat On peut définir la classe coNP en utilisant des certificats. Sur un alphabet \Sigma, un langage L est dans co-NP, s'il existe un polynôme P et une machine de Turing en temps polynomial M, tels que pour un mot x, on a équivalence entre x\in L et le fait que pour t
À 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.
Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement