Idée reçue : Si un problème est NP-complet, alors ce n’est pas la peine de s’y attaquer

Résumé : Pourquoi une affirmation aussi catégorique est-elle en partie fausse ? Revenir sur la définition des problèmes P, NP et des problèmes NP-complets aide à le comprendre.
Liste complète des métadonnées

https://hal.inria.fr/hal-01350232
Contributeur : Inria Interstices <>
Soumis le : vendredi 29 juillet 2016 - 17:44:59
Dernière modification le : mardi 24 avril 2018 - 13:36:39

Identifiants

  • HAL Id : hal-01350232, version 1

Collections

Citation

Jean-Paul Delahaye. Idée reçue : Si un problème est NP-complet, alors ce n’est pas la peine de s’y attaquer. Interstices, INRIA, 2009, 〈https://interstices.info/jcms/p_81195/idee-recue-si-un-probleme-est-np-complet-alors-ce-n-est-pas-la-peine-de-s-y-attaquer〉. 〈hal-01350232〉

Partager

Métriques

Consultations de la notice

141