Gadget (computer science)
id:
gadget-computer-science-235-2774815
title:
Gadget (computer science)
text:
In computational complexity theory, a gadget is a subunit 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 gr
brand slug:
wiki
category slug:
encyclopedia
description:
Subunit of a computational problem
original url:
https://en.wikipedia.org/wiki/Gadget_(computer_science)
date created:
date modified:
2024-03-18T03:05:13Z
main entity:
{"identifier":"Q5516347","url":"https://www.wikidata.org/entity/Q5516347"}
image:
fields total:
13
integrity:
14