Editing Reduction (complexity) (section)

{{Short description|Transformation of one computational problem to another}}
[[File:3SAT reduced too VC.svg|thumb|300px|Example of a reduction from the [[boolean satisfiability problem]] (''A'' ∨ ''B'') ∧ (¬''A'' ∨ ¬''B'' ∨ ¬''C'') ∧ (¬''A'' ∨ ''B'' ∨ ''C'') to a [[vertex cover problem]]. The blue vertices form a minimum vertex cover, and the blue vertices in the gray oval correspond to a satisfying [[truth assignment]] for the original formula.]]
In [[computability theory]] and [[computational complexity theory]], a '''reduction''' is an [[algorithm]] for transforming one [[computational problem|problem]] into another problem. A sufficiently efficient reduction from one problem to another may be used to show that the second problem is at least as difficult as the first.

Intuitively, problem ''A'' is '''reducible''' to problem ''B'', if an algorithm for solving problem ''B'' efficiently (if it exists) could also be used as a subroutine to solve problem ''A'' efficiently. When this is true, solving ''A'' cannot be harder than solving ''B''. "Harder" means having a higher estimate of the required computational resources in a given context (e.g., higher [[time complexity]], greater memory requirement, expensive need for extra hardware processor cores for a parallel solution compared to a single-threaded solution, etc.). The existence of a reduction from ''A'' to ''B'' can be written in the shorthand notation ''A'' ≤<sub>m</sub> ''B'', usually with a subscript on the ≤ to indicate the type of reduction being used (m : [[many-one reduction]], p : [[polynomial reduction]]).

The mathematical structure generated on a set of problems by the reductions of a particular type generally forms a [[preorder]], whose [[equivalence class]]es may be used to define [[Turing degree|degrees of unsolvability]] and [[complexity class]]es.