Gadget (computer science)
Encyclopedia
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.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, gadgets are often used to construct reductions
Reduction (complexity)
In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. Depending on the transformation used this can be used to define complexity classes on a set of problems....
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
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
use gadgets that represent variables and clauses of the 3-satisfiability instance; the gadgets themselves are "graph pieces" built from vertices and edges.