✢ Problem Reduction
Learning Objectives
At the end of this sub-unit, students should
- appreciate the idea of problem reduction
Map Problem P to P'
This idea of thinking in terms of patterns can actually be thought of as a problem reduction. In problem reduction, we are looking at a problem \(P\) and we are trying to find the solution \(S\). We can find the solution using other technique including exploration. Maybe we cannot find a solution to \(P\) directly.
Maybe we also found that it is quite close to some other problem \(P'\). This problem \(P'\) is quite special because we know the solution to it, which is \(S'\). So we say that the problem \(P\) is reduced to the problem \(P'\).
In this setting, the remaining problem we have is simply just how do we use the solution \(S'\) to actually solve problem \(P\). In other words, we want to construct \(S\) from \(S'\).
We are talking about \(P\) and \(S\) quite abstractly here. By extension \(P'\) and \(S'\) are also quite abstract. In particular, \(S\) and \(S'\) need not be a value. If it is a value, then we can say that there is an operation such that \(S = F(S')\). Here, we want \(S\) and \(S'\) to actually be code. Looking at it this way, \(F\) is actually a higher-order operation that takes in a code \(S'\) and produces another code \(S\)1.
To tie this back to the idea of programming pattern, the operation \(F(S')\) may be something like generalization followed by filling in the blank to specific code to solve \(P\). By thinking about problem solving this way, we can repeat the process repeatedly. Let us say that we can see that \(P\) can be reduced to problem \(P'\) but we still do not know how to solve the problem \(P'\). Maybe this is because we have seen the problem description for \(P'\) but we did not managed to solve it completely. So we need to reduce \(P'\) further into \(P''\).
This process of reduction can be performed repeatedly until we found a problem that we can solve.
Sum to Count
Assume that we know how to solve the counting digit problem. Now we encounter the sum of digit problem. We see the similarity to the problem, so a potential design is to reduce the sum of digit problem into the counting digit problem. We may then supply additional details on what needs to be changed as a comment on the arrows.
In the future, this process of problem reduction might be more important. It is a critical technique in certain analysis of problems. For now, simply think of it as simply another way of solving problems.