Jump to content

Gadget (computer science)

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Ruud Koot (talk | contribs) at 19:30, 27 February 2012 (moved Gadget (computer science) to Component design). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computational complexity theory, component design is a proof technique often used to construct a reductions from one computational problem to another. Each element of the first problem is converted to a widget or 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.

References

  • Garey, M. R.; Johnson, D. S. (1979), "3.2.3 Component Design", Computers and Intractability: A Guide to the Theory of NP-Completeness, San Francisco, Calif.: W. H. Freeman, pp. 72–74, ISBN 0-7167-1045-5, MR 0519066.
  • Sipser, Michael (1997), Introduction to the Theory of Computation, PWS Publishing Co., p. 260.
P ≟ NP 

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Gadget_(computer_science)&oldid=479168812"