Accès plus rapide que le navigateur!
16 relations: Coloration de graphe, Complet (complexité), Couplage (théorie des graphes), Forme normale disjonctive, Graphe biparti, Hiérarchie polynomiale, Informatique théorique, Leslie Valiant, Machine de Turing non déterministe, Matrice binaire, P (complexité), Permanent (mathématiques), Problème 2-SAT, Problème P ≟ NP, Sharp-P, Théorie de la complexité (informatique théorique).
Coloration de graphe
Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente.
Nouveau!!: Sharp-P-complet et Coloration de graphe · 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!!: Sharp-P-complet et Complet (complexité) · Voir plus »
Couplage (théorie des graphes)
En théorie des graphes, un couplage ou appariement (en anglais) d'un graphe est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun.
Nouveau!!: Sharp-P-complet et Couplage (théorie des graphes) · Voir plus »
Forme normale disjonctive
En logique booléenne ou en calcul des propositions, une forme normale disjonctive ou FND (en anglais, disjunctive normal form ou DNF) est une normalisation d'une expression logique qui est une disjonction de clauses conjonctives.
Nouveau!!: Sharp-P-complet et Forme normale disjonctive · Voir plus »
Graphe biparti
En théorie des graphes, un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints U et V tels que chaque arête ait une extrémité dans U et l'autre dans V. Un graphe biparti permet notamment de représenter une relation binaire.
Nouveau!!: Sharp-P-complet et Graphe biparti · 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!!: Sharp-P-complet 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!!: Sharp-P-complet et Informatique théorique · Voir plus »
Leslie Valiant
Leslie Gabriel Valiant est un informaticien théorique britannique né le à Budapest.
Nouveau!!: Sharp-P-complet et Leslie Valiant · 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!!: Sharp-P-complet et Machine de Turing non déterministe · Voir plus »
Matrice binaire
Une matrice binaire est une matrice dont les coefficients sont soit 0, soit 1.
Nouveau!!: Sharp-P-complet et Matrice binaire · 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!!: Sharp-P-complet et P (complexité) · Voir plus »
Permanent (mathématiques)
Le permanent est un outil d'algèbre linéaire.
Nouveau!!: Sharp-P-complet et Permanent (mathématiques) · Voir plus »
Problème 2-SAT
En informatique théorique, le problème 2-SAT est un problème de décision.
Nouveau!!: Sharp-P-complet et Problème 2-SAT · 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!!: Sharp-P-complet et Problème P ≟ NP · Voir plus »
Sharp-P
Considérons une machine de Turing non-déterministe en temps polynomial pour le problème dans NP correspondant un problème 'calculer f(x)' dans #P. f(x) est le nombre d'exécutions acceptantes dans l''arbre de calcul avec le mot x en entrée. Dans l'exemple f(miaou).
Nouveau!!: Sharp-P-complet et Sharp-P · 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!!: Sharp-P-complet et Théorie de la complexité (informatique théorique) · Voir plus »
