Complexite et np completude
gkludo
Messages postés
8
Date d'inscription
Statut
Membre
Dernière intervention
-
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
bonjour a vous tous. Mon problème est le suivant je veux montrer que le problème 3 color est un problème np complet. le problème 3 color consiste a colorier tous les sommets d un graphe avec 3 couleurs de telle sorte que deux sommets adjacents n'aient jamais la même couleur.
je peux deja montrer que 3 color est np en utilisant le vérifieur suivant:
1- vérifier que chaque sommet du graphe g est colorie.
2- vérifier que le nombre de couleurs utilisées pour colorier le graphe vaut 3.
3- pour toute arête (a,b) vérifier que le sommet a a une couleur différente de celle du sommet b.
le vérifieur me coute donc en complexité o(n+m) avec n étant le nombre de sommets et m le nombre d'arêtes. je peux donc conclure que 3 color est dans NP.
La où je coince c'est sur la reduction de 3Sat a 3Color. Merci pour votre aide.
je peux deja montrer que 3 color est np en utilisant le vérifieur suivant:
1- vérifier que chaque sommet du graphe g est colorie.
2- vérifier que le nombre de couleurs utilisées pour colorier le graphe vaut 3.
3- pour toute arête (a,b) vérifier que le sommet a a une couleur différente de celle du sommet b.
le vérifieur me coute donc en complexité o(n+m) avec n étant le nombre de sommets et m le nombre d'arêtes. je peux donc conclure que 3 color est dans NP.
La où je coince c'est sur la reduction de 3Sat a 3Color. Merci pour votre aide.
A voir également:
- Https //id.sonyentertainmentnetwork.com/id/management/ (np-41772-1)
- Document id lycamobile - Forum Logiciels
- Activation d'une carte SIM ✓ - Forum Mobile
- Id telephone - Guide
- Activer ma carte SIM lycamobile ✓ - Forum Mobile
- Https//www.windows.com/stopcode - Guide
1 réponse
Bonjour,
"complexité o(n+m) ... je peux donc conclure que 3 color est dans NP."
C'est un peu loin tout ça, mais en quoi une complexité polynomiale O(n+m) te permet d'affirmer que ton problème n'est pas polynomialement réductible ?
Il me semble que tu ne peux l'affirmer que si ton problème est équivalent à un autre problème NP (3-sat par exemple), mais si l'équivalence en O(n+m) se faisait par rapport à un problème P, cela en ferait un problème P aussi, pas NP...
"complexité o(n+m) ... je peux donc conclure que 3 color est dans NP."
C'est un peu loin tout ça, mais en quoi une complexité polynomiale O(n+m) te permet d'affirmer que ton problème n'est pas polynomialement réductible ?
Il me semble que tu ne peux l'affirmer que si ton problème est équivalent à un autre problème NP (3-sat par exemple), mais si l'équivalence en O(n+m) se faisait par rapport à un problème P, cela en ferait un problème P aussi, pas NP...
Exemple : (x ∨ y ∨ ¬z) ∧ (¬x ∨ ¬y ∨ z) peut se résoudre en trouvant la 3-coloration du graphe suivant.