Discussion:Liste de problèmes NP-complets
Tout ou partie de cet article est issu de la traduction de l'article sous licence CC-BY-SA « (en) List of NP-complete problems » dans sa version du 14 octobre 2006.
Consultez l'historique de la page originale pour connaître la liste de ses auteurs.
Cet article est indexé par les projets Informatique et Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | Élevée |  | Informatique (discussion • critères • liste • stats • hist. • comité • stats vues) |
| À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) | |
Cet article comporte une liste de tâches suggérées :
Votre aide est la bienvenue pour corriger les liens, présents dans l'article, vers les pages d'homonymie Sift ⇒ Quelques explications pour effectuer ces corrections. -- 30 décembre 2014 à 12:30 (CET)
Peut être certaines erreurs dans l'article ?
modifier-Je ne suis pas sur, mais il me semble que trouver le PGCD de deux nombres ce fait en temps polynomiale (n²) -Savoir si une équation diophantienne admet une solution ne me semble même pas décidable alors NP-complet ? ( si une equation diophantienne n'a pas de solution , un algo glouton tourne a l'infinie)
Je sais que cet article n'est qu'une traduction anglaise, mais qq pourrait il confirmer ou infirmé mes dires avant une modification !
Je vous remercie .
Spécial:Contributions/129.175.7.232, le 18 juin 2008 à 08:43.
Je rajouterai que la programmation linéaire est dans P (cf article sur la programmation linéaire), il faudrait donc préciser "en nombres entiers"
Spécial:Contributions/91.199.242.236, le 29 décembre 2010 à 11:36.
NP-complet ou NP-difficile ?
modifierJe ne suis pas spécialiste de complexité algorithmique mais il me semble qu'il y a ici des problèmes qui sont connus pour être NP-difficiles mais dont on ne sait pas s'ils sont NP-complets (ou cela dépend de telle ou telle formulation du problème). exemple : le problème de voyageur de commerce. --Baba Arouj (discuter) 20 janvier 2021 à 12:30 (CET)