# Computational Complexity Reduction Algorithm

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

**AKA:**Computational Complexity Reduction.**See:**Computational Complexity Class, Computability Theory, Computational Complexity Theory, Algorithm, Computational Problem, Time Complexity, Mapping Reduction, Polynomial Reduction, Preorder, Equivalence Class, Turing Degree.

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

- In computability theory and computational complexity theory, a