Problèmes industriels et réduction polynomiale

  • Satisfiability
    • Clique
      • Set packing
      • Vertex cover
        • Set covering
        • Feedback arc set
        • Feedback node set
        • Directed hamiltonian 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
Contenu de va-et-vient

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 (par réduction polynomiale).

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’).

réduction polynomiale 21 problèmes de karp

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

Partager
fr_FRFR
%d blogueurs aiment cette page :