Que signifie «gadget» dans la réduction NP-hard?

Cette question n'est peut-être pas technique. En tant que locuteur non natif et TA pour la classe d'algorithmes, je me suis toujours demandé ce que signifie gadget dans «gadget de clause» ou «gadget variable». Le dictionnaire dit qu'un gadget est une machine ou un appareil, mais je ne sais pas quelle signification familière il a dans le contexte de la preuve NP-complète.

Un "gadget" est un petit appareil spécialisé pour une tâche particulière. Dans les preuves de dureté NP, lors de la réduction du problème A au problème B, le terme familier "gadget" fait référence à de petites instances (partielles) du problème B qui sont utilisées pour "simuler" certains objets du problème A. Par exemple, lorsque en réduisant 3SAT à 3-COLORING, les gadgets de clause sont de petits graphiques qui sont utilisés pour représenter les clauses de la formule d'origine et les gadgets variables sont de petits graphiques qui sont utilisés pour représenter les variables de la formule d'origine. Afin de garantir que la réduction est correcte, les gadgets doivent être des graphiques qui peuvent être tricolores de manière très spécifique. Par conséquent, nous considérons ces petits graphiques comme des appareils qui effectuent une tâche spécialisée.

Dans de nombreux cas, la principale difficulté pour prouver la dureté NP est la construction de gadgets appropriés. Parfois, ces gadgets sont compliqués et moyennement grands. Le processus créatif de création de tels gadgets est parfois appelé «gadgeteering».

Une définition formelle des gadgets pour les réductions d'optimisation NP apparaît ici:

L. Trevisan, GB Sorkin, M. Soudan, DP Williamson. Gadgets, approximation et programmation linéaire . SIAM J. on Computing, 29 (6): 2074-2097, 2000