Editing Reductionism (section)

=== In computer science ===
The role of reduction in [[computer science]] can be thought as a precise and unambiguous mathematical formalization of the philosophical idea of "[[#Types|theory reductionism]]". In a general sense, a problem (or set) is said to be reducible to another problem (or set), if there is a computable/feasible method to translate the questions of the former into the latter, so that, if one knows how to computably/feasibly solve the latter problem, then one can computably/feasibly solve the former. Thus, the latter can only be at least as "[[NP-hardness|hard]]" to solve as the former.

Reduction in [[theoretical computer science]] is pervasive in both: the mathematical abstract foundations of computation; and in real-world [[Analysis of algorithms|performance or capability analysis of algorithms]]. More specifically, reduction is a foundational and central concept, not only in the realm of mathematical logic and abstract computation in [[Computability theory|computability (or recursive) theory]], where it assumes the form of e.g. [[Turing reduction]], but also in the realm of real-world computation in time (or space) complexity analysis of algorithms, where it assumes the form of e.g. [[polynomial-time reduction]]. Further, in the even more practical domain of software development, reduction can be seen as the inverse of composition and the conceptual process a programmer applies to a problem in order to produce an alogrithm which solves the problem using a composition of existing algorithms (encoded as subroutines, or subclasses).