Problèmes industriels et réduction polynomiale

Les problèmes de la recherche opérationnelle, et plus généralement de l’aide à la décision sont souvent Np-complet, c’est-à-dire que l’on ne connaît pas d’algorithmes permettant de trouver une solution optimale en temps polynomial, mais on sait obtenir une solution réalisable en temps polynomiale.

Les liens suivants présentent les 21 problèmes de Karp ainsi que leur réduction. Je vous invite à lire ce cours avant de prendre connaissance des problèmes.

Réduction et présentation des 21 problèmes de Karp :

  • Satisfiability
    • Clique
      • Set packing
      • Vertex cover
        • Set covering
        • Feedback arc set
        • Feedback node set
        • Directed hamiltonian circuit
          • Undirected hamiltonien circuit
  • 0-1 interger programming
  • 3-SAT
    • Chromatic number
      • Clique cover
      • Exact cover
        • Matching 3D
        • Steiner tree
        • Hitting set
        • Knapsack
          • Job sequencing
          • Partition
            • Max-cut

Pour plus d’informations sur les problèmes industriels Np-complet, je vous invite à lire le livre de Garey et Johnson : Computers and Intractability : A guide to the Theory of NP-Completeness.

Complexité polynomiale

Les problèmes sont décidables, c’est-à-dire que l’on peut formuler le problème de telle façon à ce que la réponse soit Oui ou Non. La complexité de ses problèmes sera considéré dans le pire cas.

Un algorithme est de complexité polynomiale s’il existe un polynôme P tel que le nombre d’instructions élémentaires effectuées lors de son exécution sur une instance de taille n soit au plus P(n). Un problème est de complexité polynomiale s’il existe un algorithme de complexité polynomiale le résolvant. Il est important de souligner que la représentation des structures de données utilisées n’influe pas la complexité.

 Réduction polynomiale

Un problème de décision P se réduit à un problème de décision P’ s’il existe un algorithme polynomial R qui transforme toute entrée u de P en une entrée u’=R(u) de P’ telle que u∈Oui(P) ⇔ u’∈Oui(P’).

reduc

Cela suggère l’implication suivante : s’il existe un algorithme polynomial pour P’, alors il en existe aussi un pour P.

Publicités