Accès plus rapide que le navigateur!
26 relations: Certificat (complexité), Classe de complexité, Co-NP, Complexité descriptive, Graphe hamiltonien, Hiérarchie polynomiale, Informatique théorique, Liste de problèmes NP-complets, Machine de Turing, Machine de Turing non déterministe, NTIME, P (complexité), Polynôme, Problème de décision, Problème du voyageur de commerce, Problème NP-complet, Problème P ≟ NP, Problème SAT, PSPACE, Réduction (complexité), Réduction polynomiale, Système de preuve interactive, Théorème de Fagin, Théorème de Karp-Lipton, Théorème PCP, Théorie de la complexité (informatique théorique).
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!!: NP (complexité) 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!!: NP (complexité) et Classe de complexité · 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!!: NP (complexité) et Co-NP · Voir plus »
Complexité descriptive
En informatique théorique, la complexité descriptive est une branche de la théorie de la complexité et de la théorie des modèles, qui caractérise les classes de complexité en termes de logique qui permet de décrire les problèmes.
Nouveau!!: NP (complexité) et Complexité descriptive · 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!!: NP (complexité) 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!!: NP (complexité) 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!!: NP (complexité) et Informatique théorique · Voir plus »
Liste de problèmes NP-complets
Ceci est une liste des problèmes NP-complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d'un problème de décision.
Nouveau!!: NP (complexité) et Liste de problèmes NP-complets · 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!!: NP (complexité) et Machine de Turing · Voir plus »
Machine de Turing non déterministe
Une machine de Turing non déterministe est similaire à une machine de Turing habituelle, qui, elle, est déterministe, mais s'en différencie dans le fait qu'étant non déterministe elle peut avoir plusieurs transitions activables, pour un état donné.
Nouveau!!: NP (complexité) et Machine de Turing non déterministe · Voir plus »
NTIME
En théorie de la complexité, NTIME désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing non déterministe.
Nouveau!!: NP (complexité) et NTIME · Voir plus »
P (complexité)
La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques.
Nouveau!!: NP (complexité) et P (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!!: NP (complexité) 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!!: NP (complexité) et Problème de décision · Voir plus »
Problème du voyageur de commerce
Le problème de voyageur de commerce: calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois.
Nouveau!!: NP (complexité) et Problème du voyageur de commerce · Voir plus »
Problème NP-complet
En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes.
Nouveau!!: NP (complexité) et Problème NP-complet · 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!!: NP (complexité) et Problème P ≟ NP · Voir plus »
Problème SAT
consulté le.
Nouveau!!: NP (complexité) et Problème SAT · Voir plus »
PSPACE
En informatique théorique, plus précisément en théorie de la complexité, PSPACE est la classe de complexité des problèmes de décision décidés par une machine de Turing déterministe avec un espace polynomial.
Nouveau!!: NP (complexité) et PSPACE · Voir plus »
Réduction (complexité)
En calculabilité et en théorie de la complexité, une réduction est un algorithme transformant une instance d'un problème algorithmique en une ou plusieurs instances d'un autre problème.
Nouveau!!: NP (complexité) et Réduction (complexité) · 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!!: NP (complexité) et Réduction polynomiale · Voir plus »
Système de preuve interactive
Un système de preuve interactive est composé de deux machines abstraites: un prouveur et un vérificateur qui s'échangent des messages. En théorie de la complexité des algorithmes, un système de preuve interactive est un protocole formel de démonstration de théorèmes qui fait intervenir deux participants qui échangent des messages.
Nouveau!!: NP (complexité) et Système de preuve interactive · Voir plus »
Théorème de Fagin
Le théorème de Fagin est un résultat de théorie de la complexité des algorithmes, montrant l'égalité de la classe NP et de la classe des problèmes exprimables en logique du second ordre existentielle, c'est-à-dire en logique du premier ordre enrichie de quantifications existentielles sur les ensembles.
Nouveau!!: NP (complexité) et Théorème de Fagin · Voir plus »
Théorème de Karp-Lipton
En théorie de la complexité, le théorème de Karp–Lipton affirme que si le problème de satisfiabilité booléenne (SAT) est résolu par une famille de circuits booléens avec un nombre polynomial de portes logiques (en la taille de la formule propositionnelle à tester), alors la hiérarchie polynomiale s’effondre au second niveau.
Nouveau!!: NP (complexité) et Théorème de Karp-Lipton · Voir plus »
Théorème PCP
En théorie de la complexité, un domaine de l'informatique théorique, le théorème PCP (acronyme de l'anglais probabilistically checkable proof, qui peut se traduire en français par « preuve vérifiable en probabilité ») est une caractérisation de la classe NP dans le contexte d'un système de preuve interactive.
Nouveau!!: NP (complexité) et Théorème PCP · 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!!: NP (complexité) et Théorie de la complexité (informatique théorique) · Voir plus »
