15
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ That's exactly what it is: a device that is used to achieve a specific (local) task in the reduction $\endgroup$ Nov 28, 2011 at 18:57

2 Answers 2

27
$\begingroup$

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."

$\endgroup$
1
  • $\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 Meir
    Oct 10, 2020 at 22:07
15
$\begingroup$

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)]

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.