Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Reduction (complexity)
Summary
In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A sufficiently efficient 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.). The existence of a reduction from A to B, can be written in the shorthand notation 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.
There are two main situations where we need to use reductions:
First, we find ourselves trying to solve a problem that is similar to a problem we've already solved. In these cases, often a quick way of solving the new problem is to transform each instance of the new problem into instances of the old problem, solve these using our existing solution, and then use these to obtain our final solution. This is perhaps the most obvious use of reductions.
Second: suppose we have a problem that we've proven is hard to solve, and we have a similar new problem. We might suspect that it is also hard to solve. We argue by contradiction: suppose the new problem is easy to solve. Then, if we can show that every instance of the old problem can be solved easily by transforming it into instances of the new problem and solving those, we have a contradiction.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related courses (5)
MSE-101(a): Materials:from chemistry to properties
Ce cours permet l'acquisition des notions essentielles relatives à la structure de la matière, aux équilibres et à la réactivité chimique en liaison avec les propriétés mécaniques, thermiques, électri
ENV-202: Microbiology for engineers
"Microbiology for engineers" covers the main microbial processes that take place in the environment and in treatment systems. It presents elemental cycles that are catalyzed by microorganisms and that
CH-335: Asymmetric synthesis and retrosynthesis
La première partie du cours décrit les méthodes classiques de synthèse asymétrique. La seconde partie du cours traite des stratégies de rétrosynthèse basées sur l'approche par disconnection.
Related lectures (76)
Vector: Features and Manipulation
Explores the features and manipulation of dynamic arrays (vectors), emphasizing efficient techniques and trade-offs involved.
Linear Algebra in 2D: Reduction Applications
Explores the application of reductions in R² for linear functions, emphasizing the calculation of f composed n times with itself.
Promise Constraint Satisfaction and Width
Covers Promise Constraint Satisfaction Problems complexity, width, graph coloring, polymorphisms, and algorithms.
Related publications (172)
Related people (31)
Related units (1)