O que significa 'gadget' na redução NP-hard?

Esta pergunta pode não ser técnica. Como um falante não-nativo e um AT para a classe de algoritmos, sempre me perguntei o que significa gadget em 'cláusula gadget' ou 'variável gadget'. O dicionário diz que um gadget é uma máquina ou um dispositivo, mas não tenho certeza do significado coloquial que ele tem no contexto da prova de NP-complete.

Um "gadget" é um pequeno dispositivo especializado para alguma tarefa específica. Nas provas de dureza NP, ao fazer uma redução do problema A para o problema B, o termo coloquial "gadget" refere-se a instâncias pequenas (parciais) do problema B que são usadas para "simular" certos objetos no problema A. Por exemplo, quando reduzindo 3SAT para 3-COLORING, os gadgets de cláusula são pequenos gráficos usados ​​para representar as cláusulas da fórmula original e os gadgets variáveis ​​são pequenos gráficos usados ​​para representar as variáveis ​​da fórmula original. Para garantir que a redução esteja correta, os gadgets precisam ser gráficos que podem ter três cores de maneiras muito específicas. Por isso, pensamos nesses pequenos gráficos como dispositivos que executam uma tarefa especializada.

Em muitos casos, a principal dificuldade de provar a dureza NP é a construção de dispositivos apropriados. Às vezes, esses gadgets são complicados e moderadamente grandes. O processo criativo de criar esses gadgets às vezes é chamado de "gadgeteering".

Uma definição formal de Gadgets para reduções de otimização de NP aparece aqui:

L. Trevisan, GB Sorkin, M. Sudão, DP Williamson. Gadgets, Aproximação e Programação Linear . Universidade Federal do Rio Grande do Sul.