Gadget (computer science)

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.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Inspector Gadget (film) — Inspector Gadget Theatrical release poster Directed by David Kellogg Produced by …   Wikipedia

  • History of science fiction films — The history of science fiction films parallels that of the motion picture industry as a whole, although it took several decades before the genre was taken seriously. Since the 1960s, major science fiction films have succeeded in pulling in large… …   Wikipedia

  • The Science of Spying — is a touring exhibition produced by The Science of..., a joint venture between the Science Museum (London) and Fleming Media. The Science of Spying opened at the Science Museum on 10 February 2007and a duplicate exhibition opened in the The… …   Wikipedia

  • Jaron Lanier — Lanier performing at the Garden of Memory Solstice Concert in June, 2009 Born May 3, 1960 (1960 05 03) (age 51) New York City …   Wikipedia

  • MIT in popular culture — The Massachusetts Institute of Technology (MIT), an educational and research institution in Cambridge, Massachusetts, has been referenced in many works of cinema, television and the written word. MIT s overall reputation has greater influence on… …   Wikipedia

  • Speech synthesis — Stephen Hawking is one of the most famous people using speech synthesis to communicate Speech synthesis is the artificial production of human speech. A computer system used for this purpose is called a speech synthesizer, and can be implemented… …   Wikipedia

  • Marc Laidlaw — (born 1960) is an American writer of science fiction and horror and also a computer game designer with Valve Software. He is perhaps most famous for writing Dad s Nuke and The 37th Mandala, and for working on the popular Half Life series.[1]… …   Wikipedia

  • Sintetizador del habla — Uno o varios wikipedistas están trabajando actualmente en este artículo o sección. Es posible que a causa de ello haya lagunas de contenido o deficiencias de formato. Si quieres, puedes ayudar y editar, pero por favor: antes de realizar… …   Wikipedia Español

  • Engineering — The Watt steam engine, a major driver in the Industrial Revolution, underscores the importance of engineering in modern history. This model is on display at the main building of the ETSIIM in Madrid, Spain. Engineering is the discipline, art,… …   Wikipedia

  • Ergonomics — Ergonomics: the science of designing user interaction with equipment and workplaces to fit the user. Ergonomics is the study of designing equipment and devices that fit the human body, its movements, and its cognitive abilities. The International …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”