Posté par brendel .
En réponse au journal CAPTCHA.
Évalué à 3.
Pour rappel les Problème_NP-complet sont des problèmes dont on peut vérifier si une solution au problème est valide ou non en un temps polynomiale
Non. Un problème NP-Complet appartient à la classe NP, donc on peut affirmer qu'on peut les résoudre en temps polynomiale de manière non-déterministe. Pour certain, on sait qu'on peut les résoudre en temps polynomiale de manière déterministe (ceux qui appartiennent à P) mais pas tous. Et plus précisément dans le cas des problèmes NP-Complet on ne sait pas faire.
Grosso modo leur résolution par un ordinateur consiste à générer des solutions et à les vérifier (en "brute force").
Leur résolution optimale, mais il existe des algos bien plus efficaces qui approchent l'optimale en un temps polynomiale sur machine déterministe (enfin pour la plupart des problèmes qui sont intéressants à résoudre)
Qu'en pensez-vous ? Pensez-vous que ce serais réalisable ?
# non
Posté par brendel . En réponse au journal CAPTCHA. Évalué à 3.
Non. Un problème NP-Complet appartient à la classe NP, donc on peut affirmer qu'on peut les résoudre en temps polynomiale de manière non-déterministe. Pour certain, on sait qu'on peut les résoudre en temps polynomiale de manière déterministe (ceux qui appartiennent à P) mais pas tous. Et plus précisément dans le cas des problèmes NP-Complet on ne sait pas faire.
Leur résolution optimale, mais il existe des algos bien plus efficaces qui approchent l'optimale en un temps polynomiale sur machine déterministe (enfin pour la plupart des problèmes qui sont intéressants à résoudre)
Du coup, non.