Sharp-P-complet
- Sharp-P-complet
-
#P-complet, prononcée "sharp P complet" ou "dièse P complet", est une classe de complexité en théorie de la complexité. Un problème X est dit #P-complet si et seulement s'il appartient à la classe #P, et si on peut réduire tout problème de #P à X par une réduction de comptage fonctionnant en temps polynomial. De manière équivalente, un problème X est #P-complet si et seulement s'il appartient à #P et si pour toute machine de Turing non déterministe, le problème consistant à calculer son nombre de chemins acceptants peut être réduit à X.
Les problèmes suivants sont des exemples de problèmes #P-complets :
- Combien une formule FND donnée admet-elle d'assignements valides ?
- Combien une formule 2-SAT donnée admet-elle d'assignements valides ?
- Quel est la valeur du permanent d'une matrice donnée à coefficients valant 0 ou 1 ?
- Combien de couplages parfaits admet un graphe biparti donné ?
- Combien de k-coloriages admet un graphe donné ?
L'existence d'un algorithme polynomial pour un problème #P-complet impliquerait P=PH, et donc P=NP. Actuellement, aucun algorithme de la sorte n'est connu.
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Sharp-P-complet de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Sharp-p — #P, prononcé sharp P (ou dièse P ), est une classe de complexité. Contrairement à la plupart des autres classes de complexité, ce n est pas une classe de problèmes de décision mais une classe de fonctions calculables. Il s agit de compter le… … Wikipédia en Français
Sharp (syndrome) — Syndrome de Sharp Syndrome de Sharp CIM 10: M35.1 {{{CIM10}}}.0 {{{X.0}}} … Wikipédia en Français
Sharp syndrome — Syndrome de Sharp Syndrome de Sharp CIM 10: M35.1 {{{CIM10}}}.0 {{{X.0}}} … Wikipédia en Français
Sharp-P — #P, prononcé sharp P (ou dièse P ), est une classe de complexité. Contrairement à la plupart des autres classes de complexité, ce n est pas une classe de problèmes de décision mais une classe de fonctions calculables. Il s agit de compter le… … Wikipédia en Français
Syndrome de sharp — CIM 10: M35.1 {{{CIM10}}}.0 {{{X.0}}} … Wikipédia en Français
C sharp — Pour les articles homonymes, voir Sharp et .cs. C♯ … Wikipédia en Français
Syndrome de Sharp — CIM 10 : M35.1 Le syndrome de Sharp ou connectivite mixte est une association chez un patient des signes d au moins deux connectivites (maladies systémiques, maladie auto immune). Elle a été décrite pour la première fois en 1972 par Gordon… … Wikipédia en Français
Graham Sharp — Pour les articles homonymes, voir Sharp. Graham Sharp Biographie Nom complet Henry Graham … Wikipédia en Français
Kristen Sharp — Fiche d’identité … Wikipédia en Français
Richard Sharp — Pour les articles homonymes, voir Sharp. Infobox Rugbyman Richard Sharp … Wikipédia en Français
