Répondre à la discussion
Affichage des résultats 1 à 14 sur 14

NP-Complet vs NP-Difficile !!!!



  1. #1
    Polytechnicienne

    Post 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

    -----

  2. Publicité
  3. #2
    invite73192618

    Re : NP-Complet vs NP-Difficile !!!!

    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.

  4. #3
    invite73192618

    Re : NP-Complet vs NP-Difficile !!!!

    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...

  5. #4
    jobherzt

    Re : NP-Complet vs NP-Difficile !!!!

    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.

  6. A voir en vidéo sur Futura
  7. #5
    Polytechnicienne

    Re : NP-Complet vs NP-Difficile !!!!

    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

  8. #6
    jobherzt

    Re : NP-Complet vs NP-Difficile !!!!

    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.

  9. Publicité
  10. #7
    Polytechnicienne

    Re : NP-Complet vs NP-Difficile !!!!

    moi c ke g compri :
    np-complet appartient à np-difficile appartient à np ??????

  11. #8
    jobherzt

    Re : NP-Complet vs NP-Difficile !!!!

    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.

  12. #9
    Gwyddon

    Re : NP-Complet vs NP-Difficile !!!!


    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.

  13. #10
    Polytechnicienne

    Re : NP-Complet vs NP-Difficile !!!!

    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.

  14. #11
    jobherzt

    Re : NP-Complet vs NP-Difficile !!!!

    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.

  15. #12
    Polytechnicienne

    Re : NP-Complet vs NP-Difficile !!!!

    merci merci
    j'ai compri, .... a bientot! et puis etre polytechnicien ne veut pas dire etre parfait, je dois passer par des moments pareils pour comprendre...

  16. Publicité
  17. #13
    ame1560

    Re : NP-Complet vs NP-Difficile !!!!

    Citation Envoyé par jobherzt Voir le message
    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.
    salut;
    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é;
    @+

  18. #14
    arbia

    Re : NP-Complet vs NP-Difficile !!!!

    Citation Envoyé par Polytechnicienne Voir le message
    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
    * le probleme de classe P si (DE) est de complexité polynomiale
    *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.

Discussions similaires

  1. Problème NP-complet indécidable
    Par benoir126 dans le forum Mathématiques du supérieur
    Réponses: 15
    Dernier message: 24/05/2014, 10h22
  2. Espace de Baire non complet?
    Par indian58 dans le forum Mathématiques du supérieur
    Réponses: 22
    Dernier message: 21/01/2008, 17h03
  3. La famille au grand complet !
    Par invite78632345678 dans le forum Matériel astronomique et photos d'amateurs
    Réponses: 8
    Dernier message: 02/05/2006, 17h28
  4. cours complet de maths
    Par simetoile dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 17/02/2006, 20h51