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.
What does 'gadget' mean in NP-hard reduction?
cc.complexity theory;np hardness;terminology;reductions
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.