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

Temps NP.



  1. #1
    Noress

    Temps NP.


    ------

    Bonjour,

    Un algorithme NP s'exécute en temps NP.

    * Lorsque la complexité du problème NP croît, le temps NP de résolution peut-il être constant ?
    ** Peut-on mesurer le temps NP de résolution, car j'ai parfois l'impression que c'est comme essayer de mesurer une courbe en ayant qu'un seul point de celle-ci.

    Merci.

    -----

  2. #2
    minushabens

    Re : Temps NP.

    Citation Envoyé par Noress Voir le message
    Lorsque la complexité du problème NP croît, le temps NP de résolution peut-il être constant ?
    une fonction constante est bien un polynôme.

  3. #3
    Schrodies-cat

    Re : Temps NP.

    Il me semble utile de préciser les notions par un exemple:

    Considérons on problème NP non P, ou du moins réputé tel (si vous parvenez à le démontrer ou à démontrer le contraire , il y a un million de dollars pour vous).
    Le coloriage d'un graphe en 3 couleurs.
    Il est évident que plus votre graphe sera important, plus le temps de calcul sera long pour trouver un coloriage ou prouver que c'est impossible. Le temps de calcul dépend donc de l'instance (le graphe) du problème
    On ne connait pour cela pour l'instant que des algorithmes de complexité exponentielle pour ce problème, c'est à dire pour les quels le temps de calcul maximum en fonction de la taille du graphe est exponentiel.

    La complexité d'un problème ou plus simplement d'un algorithme est donc une fonction de la taille des données.

    Il est souvent difficile de déterminer la complexité d'un algorithme, et plus encore celle d'un problème, qui est celle des meilleurs algorithmes le résolvant.
    Dernière modification par Schrodies-cat ; 02/05/2016 à 12h28.
    Il n'est pire sot que qui ne veut pas comprendre .

Discussions similaires

  1. Actualité - Observer les vents en temps réel : quel temps fera-t-il demain ?
    Par V5bot dans le forum Commentez les actus, dossiers et définitions
    Réponses: 3
    Dernier message: 13/01/2014, 09h40
  2. Réponses: 10
    Dernier message: 22/12/2011, 11h08
  3. Réponses: 3
    Dernier message: 30/07/2011, 17h51
  4. Réponses: 1
    Dernier message: 14/01/2010, 17h35