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.
$\begingroup$
$\endgroup$
1
asked Nov 28, 2011 at 18:49
-
5$\begingroup$ That's exactly what it is: a device that is used to achieve a specific (local) task in the reduction $\endgroup$– Suresh VenkatNov 28, 2011 at 18:57
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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."
-
$\begingroup$ Good answer. I think one can add a little more: A "clause gadget" for a specific clause is an instance that forces any legal solution of 3-COLORING to satisfy at least one literal of that clause. A "variable gadget" prevents a legal solution to satisfy both that variable and its negation. $\endgroup$– Or MeirOct 10, 2020 at 22:07
$\begingroup$
$\endgroup$
0
A formal definition of Gadgets for NP optimization reductions appears here:
L. Trevisan, G.B. Sorkin, M. Sudan, D.P. Williamson. Gadgets, Approximation, and Linear Programming. SIAM J. on Computing, 29(6):2074-2097, 2000 [(doi, freely available)]
answered Nov 28, 2011 at 19:20