Idée reçue : Si un problème est NP-complet, alors ce n’est pas la peine de s’y attaquer - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Interstices Année : 2009

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

Jean-Paul Delahaye
Laboratoire d'Informatique Fondamentale de Lille

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.

Domaines

Informatique [cs]

inria Interstices  : Connectez-vous pour contacter le contributeur

https://inria.hal.science/hal-01350232

Soumis le : vendredi 29 juillet 2016-17:44:59

Dernière modification le : vendredi 24 mars 2023-14:53:02

Fichier non déposé

Dates et versions

hal-01350232 , version 1 (29-07-2016)

Identifiants

  • HAL Id : hal-01350232 , version 1

Citer

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, 2009. ⟨hal-01350232⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

UNIV-LILLE3 CNRS INRIA INRIA-MECSCI
106 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More