Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

Used in questions asking for efficient (polynomial-time) reductions between computational problems.

In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem.

If the reduction is further restricted to run in polynomial-time, then it is called a polynomial-time reduction.