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