Previous: optimization/search/decision problems, Up: Hard Problems
A reduction of problem A to problem B, (A → B), is just an algorithm for A which uses an algorithm for B as a subroutine.
Why would we call an ordinary algorithm a reduction? The point is that we design the reduction not in order to solve problem A, but in order to learn something about problem B. We generally develop reductions when we don't even know a satisfactory algorithm for problem B!
For example, we will next show that problem A = Sorting can be reduced to problem B = finding the convex hull of a set of points in the plane. The point of this is not to get a new sorting algorithm. Rather it is to show that finding convex hulls is at least as hard as sorting numbers.
By contrast, consider problem A = Sorting and problem B = merging 2 sorted sequences. The mergesort algorithm solves problem A by using a function merge() that solves problem B. However we don't call this a reduction because the point of mergesort is to solve the sorting problem and we do have a good algorithm for merging.
Principle: The point of reducing problem B to problem A (when you don't have a satisfactory algorithm for A) is to show A is at least as hard as B.