Gadget (informatique)

En informatique théorique, et plus précisément en théorie de la complexité, un gadget est un morceau d'une instance qui simule le comportement d'un autre problème algorithmique. Les gadgets sont utilisés dans les réductions, notamment pour démontrer la NP-dureté. La technique component design [1] est une méthode pour construire des réductions en utilisant des gadgets.

Pour les articles homonymes, voir Gadget (homonymie).

Selon Szabó [2], l'utilisation de gadgets remonte à un article de 1954, de W. T. Tuttle de théorie des graphes. Dans cet article[3], Tuttle propose des gadgets pour réduire le problème de recherche de sous-graphes au problème de couplage. Cependant la terminologie "gadget" semble avoir une origine plus récente et n'apparait pas dans l'article de Tuttle de 1954.

Exemple
A gauche, les deux gadgets de la réduction de 3SAT vers 3-coloration. A droite, l'instance de 3-coloration correspondant à la formule (x ∨ y ∨ ~z) ∧ (~x ∨ ~y ∨ z), obtenue en collant plusieurs gadgets.

Dans cette section, nous allons donner les gadgets de la réduction du problème 3-SAT au problème de 3-coloration d'un graphe, comme donné dans le livre d'Oded Goldreich[4].

Notes et références
  1. (en) M. R. Garey et D. S. Johnson, Computers and intractability : a guide to the theory of NP-completeness, San Francisco, Calif., W. H. Freeman, , 72–74 p. (ISBN 0-7167-1045-5, Math Reviews 519066), chap. 3.2.3 (« Component Design »).
  2. Jácint Szabó, « Good characterizations for some degree constrained subgraphs », Journal of Combinatorial Theory, vol. 99, no 2,‎ (DOI 10.1016/j.jctb.2008.08.009, Math Reviews 2482961).
  3. W. T. Tutte, « A short proof of the factor theorem for finite graphs », Canadian Journal of Mathematics, vol. 6,‎ (DOI 10.4153/CJM-1954-033-3, Math Reviews 0063008).
  4. This reduction is described in Oded Goldreich, Computational Complexity : A Conceptual Perspective, Cambridge University Press, (lire en ligne), Proposition 2.27, p. 81.
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.