Gadget (informatique)

Le gadget informatique est un morceau d'une instance simulant un problème algorithmique.

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
A gauche, les deux gadgets de la réduction de 3SAT vers 3-coloration. A droite, l'instance de 3-coloration correspondant à la formule (xy ∨ ~z) ∧ (~x ∨ ~yz), 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

modifier
  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, MR 519066), chap. 3.2.3 (« Component Design »).
  2. 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).
  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, MR 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.