NP-Complet vs NP-Difficile !!!!
Bonjour tout le monde.
Franchement, je voudrai savoir s'il ya une différence en tre un problème NP-Complet et un problème NP-Difficile?
si le cas , merci de me présicer quelle est la diférence...
ET est ce que un probleme NP (tout court) existe
merci beaucoup
à vos claviers
C'est la même chose: ces problèmes sont dans la classe des NP (mais tous les problèmes de NP ne sont pas NP-difficile/Complet), semblent particulièrement difficiles à résoudre (d'où leur nom), et présentent la particularité suivante: trouver une solution polynomiale à un seul d'entre eux équivaut à résoudre tout les problèmes de NP (d'où leur nom!).
Est-ce que ça existe? Oui bien sur par définition, mais on ne sait pas si c'est vraiment un type de problème plus difficile à résoudre que les problèmes P.
Ralala mes excuses mais apparement ma réponse est fausse: les NP-difficiles pourraient être encore plus difficile que les NP-complets...
[modegotorévisionetsort=ON...
en fait, pour faire simple :
NP est une classe de complexité, donc il existe des problemes qui sont NP et d'autre qui ne le sont pas.
les problemes NP-complets sont des problemes qui sont NP et qui sont specialement difficile. en fait, ce sont meme les plus difficile parmi NP, et ils sont tous equivalents entre eux.
un probleme est dit NP difficile s'il est au moins aussi difficile qu'un probleme NP complet. ce qui signifie qu'un pb NP difficile n'est meme pas forcement NP.
donc tous les NP complets sont NP difficiles, mais l'inverse n'est pas vrai.
merci , pour vos réponses....
mais j'ai toujours pas compri la différence entre np-difficile et np-complet!
np-complet implique np- difficile mais pas le contraire , ok
mais c'est quoi la différence !!!!
helppppppppppp! merci
ca me ferait plaisir que tu lises les messages en entiers avant de hurler des "heeeelp" de 15 m de long... j'ai donné plusieurs fois la reponse a ta question : un probleme NP complet est un probleme NP, ce qui n'est pas forcement le cas d'un probleme NP difficile.
donc un probleme NP difficile est au moins aussi difficile qu'un probleme NP complet, mais peut etre encore plus difficile.
moi c ke g compri :
np-complet appartient à np-difficile appartient à np ??????
essaie de faire des vraies phrases avec des vrais mots, et essaie de lire ce qu'on te dit. ta phrase est un non sens absolu. et je viens de te dire (2 fois) que les problemes NP difficile n'appartiennent pas en general a NP.
J'ai supprimé les deux dernières interventions, hors de propos.
Je rappelle à Polytechnicienne que le langage SMS est interdit sur ce forum, on respecte les lecteurs
Pour la modération,
Gwyddon
A quitté FuturaSciences. Merci de ne PAS me contacter par MP.
je suis désolée , le stresse pèse lourd.....
alors pourquoi , ils sont nommés NP-difficile le NP... il correspond à quoi?
alors je dois comprendre que les problemes np-difficiles ne sont pas "non deterministic polynomial" ...
Dernière modification par Gwyddon ; 09/05/2007 à 21h39.
ils ne le sont pas forcement !!!!!!
essayons de reformuler les choses :
- un probleme est Np difficile s'il est plus difficile que n'importe quel probleme qui appartient a NP. donc c'est general,
- un probleme est NP-complet si a la fois : il est NP difficile, et il appartient a NP.
le plus simple c'est de dessinner des patates :une patate qui contient tous les problemes NP. Cette patate contient en particulier les problemes P.
Les problemes NP difficiles sont ceux qui sont a l'exterieur de cette patate. les problemes NP complets sont a la frontiere, sur le trait.
j'ai compri, .... a bientot! et puis etre polytechnicien ne veut pas dire etre parfait, je dois passer par des moments pareils pour comprendre...
salut;Envoyé par jobherzt
je ne sais pas d'où vous avez eu cette idée de patate!!!!
on qualifie de "NP-Complet" les problèmes de "décision" qu'on peut verifier une solution donnée en temps polynômial.La résolution de l'un de ces problèmes en temps polynômial entraîne la résolution en temps polynômial de tout problème NP.
on qualifie de"NP-Difficile" les problèmes "d'optimisation" dont le problème de décision approprié est "NP-Complet".
il n ya même pas lieu de comparer les deux notions!!!
l'utilisation du nom d'une classe au lieu de celle qui lui correspond est un abus de langage propre au praticiens...mais absolument pas joli en thèorie...
en ce qui concerne l'existance des problèmes NP-Complet, bhen on s'en doute des fois!!!
merci de me corrigé;
@+
* le probleme de classe P si (DE) est de complexité polynomialeBonjour tout le monde.
Franchement, je voudrai savoir s'il ya une différence en tre un problème NP-Complet et un problème NP-Difficile?
si le cas , merci de me présicer quelle est la diférence...
ET est ce que un probleme NP (tout court) existe
merci beaucoup
à vos claviers
*le probleme est de classe NP si (DE) est ardu. la classe des problemes des NP complets est incluse dans la classe NP
*le probleme est de classe NP-ardu si (DE) est NP-Complet.
