Reduction (complexity)

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.

Intuitively, problem A is reducible to problem B if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently. When this is true, solving A cannot be harder than solving B. We write A ≤m B, usually with a subscript on the ≤ to indicate the type of reduction being used (m : mapping reduction, p : polynomial reduction).

Read more about Reduction (complexity):  Introduction, Definition, Properties, Types and Applications of Reductions, Examples

Other articles related to "reduction":

Reduction (complexity) - Examples - Detailed Example
... The following example shows how to use reductionfrom the halting problem to prove that a language is undecidable ... We show that E is undecidable by a reductionfrom H ...

Famous quotes containing the word reduction:

    The reduction of nuclear arsenals and the removal of the threat of worldwide nuclear destruction is a measure, in my judgment, of the power and strength of a great nation.
    Jimmy Carter (James Earl Carter, Jr.)