Computational Complexity Reduction Algorithm

From GM-RKB
Jump to: navigation, search

A Computational Complexity Reduction Algorithm is a Computational Complexity Algorithm that transforms one computational problem into less complex computational problem



References

2018

  • (Wikipedia, 2018) ⇒ https://en.wikipedia.org/wiki/Reduction_(complexity) Retrieved:2018-4-1.
    • In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A 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 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. "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.).

      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).

      The mathematical structure generated on a set of problems by the reductions of a particular type generally forms a preorder, whose equivalence classes may be used to define degrees of unsolvability and complexity classes.