Logo
Unionpédia
Communication
Disponible sur Google Play
Nouveau! Téléchargez Unionpédia sur votre appareil Android™!
Installer
Accès plus rapide que le navigateur!
 

Co-NP

Indice Co-NP

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é.

19 relations: Certificat (complexité), Classe de complexité, Clique (théorie des graphes), Co-NP, Complémentaire (complexité), Complet (complexité), Graphe hamiltonien, Hiérarchie polynomiale, Informatique théorique, Machine de Turing, NP (complexité), Polynôme, Problème de décision, Problème P ≟ NP, Problème SAT, Réduction polynomiale, Test de primalité, Théorie de la complexité (informatique théorique), Validité (logique).

Certificat (complexité)

En informatique théorique, plus précisément en théorie de la complexité des algorithmes, un certificat est, de façon simplifiée, une information permettant de certifier que l'entrée est correcte.

Nouveau!!: Co-NP et Certificat (complexité) · Voir plus »

Classe de complexité

En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource.

Nouveau!!: Co-NP et Classe de complexité · Voir plus »

Clique (théorie des graphes)

Exemple de graphe possédant une 3-clique (en rouge): les trois sommets de ce sous-graphe sont tous adjacents deux-à-deux. Exemple de « biclique »: le graphe biparti complet K3,3. Une clique d'un graphe non orienté est, en théorie des graphes, un sous-ensemble des sommets de ce graphe dont le sous-graphe induit est complet, c'est-à-dire que deux sommets quelconques de la clique sont toujours adjacents.

Nouveau!!: Co-NP et Clique (théorie des graphes) · Voir plus »

Co-NP

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é.

Nouveau!!: Co-NP et Co-NP · Voir plus »

Complémentaire (complexité)

En théorie de la complexité (un domaine de l'informatique théorique), on parle du complémentaire d'une classe C, noté co-C ou coC, pour désigner l'ensemble des langages complémentaires des langages de la classe.

Nouveau!!: Co-NP et Complémentaire (complexité) · Voir plus »

Complet (complexité)

En informatique théorique, et notamment en théorie de la complexité, un problème complet pour une classe de complexité est un problème de décision qui fait partie des problèmes les plus difficiles à résoudre de cette classe.

Nouveau!!: Co-NP et Complet (complexité) · Voir plus »

Graphe hamiltonien

solides de Platon, le dodécaèdre est représenté par un graphe hamiltonien. graphe grille 8x8. En mathématiques, dans le cadre de la théorie des graphes, un chemin hamiltonien d'un graphe orienté ou non orienté est un chemin qui passe par tous les sommets une fois et une seule.

Nouveau!!: Co-NP et Graphe hamiltonien · Voir plus »

Hiérarchie polynomiale

En théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP.

Nouveau!!: Co-NP et Hiérarchie polynomiale · Voir plus »

Informatique théorique

Une représentation artistique d'une machine de Turing. Les machines de Turing sont un modèle de calcul. L'informatique théorique est l'étude des fondements logiques et mathématiques de l'informatique.

Nouveau!!: Co-NP et Informatique théorique · Voir plus »

Machine de Turing

En informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur.

Nouveau!!: Co-NP et Machine de Turing · Voir plus »

NP (complexité)

La classe NP est une classe très importante de la théorie de la complexité.

Nouveau!!: Co-NP et NP (complexité) · Voir plus »

Polynôme

Courbe représentative d'une fonction cubique. En mathématiques, un polynôme est une expression formée uniquement de produits et de sommes de constantes et d'indéterminées (aussi appelées variables), habituellement notées X, Y, Z, etc.

Nouveau!!: Co-NP et Polynôme · Voir plus »

Problème de décision

En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ».

Nouveau!!: Co-NP et Problème de décision · Voir plus »

Problème P ≟ NP

Représentation visuelle des deux configurations possibles. Le problème est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général.

Nouveau!!: Co-NP et Problème P ≟ NP · Voir plus »

Problème SAT

consulté le.

Nouveau!!: Co-NP et Problème SAT · Voir plus »

Réduction polynomiale

Une réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité.

Nouveau!!: Co-NP et Réduction polynomiale · Voir plus »

Test de primalité

date.

Nouveau!!: Co-NP et Test de primalité · Voir plus »

Théorie de la complexité (informatique théorique)

P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée…) requis par un algorithme pour résoudre un problème algorithmique.

Nouveau!!: Co-NP et Théorie de la complexité (informatique théorique) · Voir plus »

Validité (logique)

En logique, la validité est la manière dont les prémisses et la conclusion concordent logiquement dans les arguments réussis.

Nouveau!!: Co-NP et Validité (logique) · Voir plus »

Redirections ici:

Classe co-NP, Co-NP-complet, NP = co-NP.

SortantEntrants
Hey! Nous sommes sur Facebook maintenant! »