What is reducibility?
In The Karate Kid (Sony Pictures, 1984), Mr. Miyagi teaches Daniel to do defensive blocks by having him repeatedly wax Miyagi’s car. The idea is to learn how to block an attack, starting by training yourself to apply and remove car wax. Start with the problem you want to solve (blocking an attacker’s approach) and turn it into a different problem (rubbing metal to make it shine). At first sight, the two problems seem to be unrelated, but in the movie, Daniel learns that the skills underlying both problems are identical. A solution to the waxing problem tells Daniel how to solve the defensive blocking problem.
In the formal terminology of algorithms, we might say that the defensive blocking problem is reducible to the car-waxing problem. The word reducible suggests that, in some way, waxing a car is simpler than defensive blocking. Indeed, the simplicity of polishing metal is what helps Daniel to learn movements so naturally.
In the same way...
