<p>A formal definition of Gadgets for NP optimization reductions appears here:</p>
<p>L. Trevisan, G.B. Sorkin, M. Sudan, D.P. Williamson.  <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.1673&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Gadgets, Approximation, and Linear Programming</a>. SIAM J. on Computing, 29(6):2074-2097, 2000 [(<a href="http://dx.doi.org/10.1137/S0097539797328847" rel="nofollow noreferrer">doi</a>, freely available)]</p>

CC BY-SA 4.0
2011-11-28T19:20:37.683Z
2020-10-09T17:06:54.000Z
2020-10-09T17:06:54.000Z
Mahdi Cheraghchi
<p>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.</p>

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

CC BY-SA 4.0
2020-10-10T22:07:17.710Z
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.
Or Meir
CC BY-SA 3.0
2011-11-28T20:45:46.407Z
2011-11-28T20:45:46.407Z
Daniel Marx
<p>This question may not be technical. As a non-native speaker and a TA for algorithm class, I always wondered what <i>gadget</i> 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.</p>

CC BY-SA 3.0
2011-11-28T18:57:07.963Z
That's exactly what it is: a device that is used to achieve a specific (local) task in the reduction
Suresh Venkat
<cc.complexity-theory><np-hardness><terminology><reductions>
What does 'gadget' mean in NP-hard reduction?
Federico Magallanez
# What does 'gadget' mean in NP-hard reduction?

(Asked by: username_0 on 2011-11-28)

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.

**Tags:** cc.complexity-theory, np-hardness, terminology, reductions
> **Comments:**
> **username_1**: That's exactly what it is: a device that is used to achieve a specific (local) task in the reduction  

---

## 2 answers

### Answer by username_3 on 2011-11-28. Score: 27 | Accepted answer

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

> **Comments:**
> **username_4**: 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.  

---

### Answer by username_2 on 2011-11-28. Score: 15

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.1673&rep=rep1&type=pdf). SIAM J. on Computing, 29(6):2074-2097, 2000 [([doi](http://dx.doi.org/10.1137/S0097539797328847), freely available)]


---

