Gadget (computer Science)
In computational complexity theory, a gadget is a subset of a problem instance that simulates the behavior of one of the fundamental units of a different computational problem. Gadgets are typically used to construct reductions from one computational problem to another, as part of proofs of NP-completeness or other types of computational hardness. The component design technique is a method for constructing reductions by using gadgets.
Szabó (2009) traces the use of gadgets to a 1954 paper in graph theory by W. T. Tutte, in which Tutte provided gadgets for reducing the problem of finding a subgraph with given degree constraints to a perfect matching problem. However, the "gadget" terminology has a later origin, and does not appear in Tutte's paper.
Read more about Gadget (computer Science): Example, Restricted Reductions, Optimization of Gadgets
Famous quotes containing the word gadget:
“A new gadget that lasts only five minutes is worth more than an immortal work that bores everyone.”
—Francis Picabia (1878–1953)