Gadget (computer science)

In computer science and computational complexity theory, gadgets are often used to construct reductions from one problem to another. Each element of the first problem is converted to a gadget built from elements of the second problem. For example, many reductions of 3-satisfiability to problems involving graphs use gadgets that represent variables and clauses of the 3-satisfiability instance; the gadgets themselves are "graph pieces" built from vertices and edges.