What does 'gadget' mean in NP-hard reduction? This question may not be technical. As a non-native speaker and a TA for algorithm class, I always wondered what gadget means in 'clause gadget' or 'variable gadget'. The dictionary says a gadget is a machine or a device, but I'm not sure what colloquial meaning it has in the context of NP-complete proof.
A "gadget" is a small specialized device for some particular task. In NP-hardness proofs, when doing a reduction from problem A to problem B, the colloquial term "gadget" refers to small (partial) instances of problem B that are used to "simulate" certain objects in problem A. For example, when reducing 3SAT to 3-COLORING, clause gadgets are small graphs that are used to represent the clauses of the original formula and variable gadgets are small graphs that are used to represent the variables of the original formula. In order to ensure that the reduction is correct, the gadgets have to be graphs that can be 3-colored in very specific ways. Hence we think of these small graphs as devices that perform a specialized task.

In many cases, the main difficulty of proving NP-hardness is constructing appropriate gadgets. Sometimes these gadgets are complicated and moderately large. The creative process of creating such gadgets is sometimes called "gadgeteering."