Gadget (informatique)
Cet article est une ébauche concernant l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Pour les articles homonymes, voir Gadget (homonymie).
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.
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[modifier | modifier le code]
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[modifier | modifier le code]
- (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, MR 519066), chap. 3.2.3 (« Component Design »).
- Jácint Szabó, « Good characterizations for some degree constrained subgraphs », Journal of Combinatorial Theory, series B, vol. 99, no 2, (DOI 10.1016/j.jctb.2008.08.009, MR 2482961).
- 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, MR 0063008).
- This reduction is described in Oded Goldreich, Computational Complexity : A Conceptual Perspective, Cambridge University Press, (lire en ligne), Proposition 2.27, p. 81.
