¶ reduction Posted 21 years, 2 months ago on October 8, 2004
Savage loved to harp on and on about reduction. Harry did too. Reduce Knapsack to 3SAT to CSAT and stuff like that. They'd always go on and on about the importance, beauty, and elegance of reduction. And it was always kinda neat and stuff to me, but that's about it. Just neat.

The more you think about it, though, the more apparent it becomes that reduction is quite often not just a tool, but the essence of solving a problem. Being able to reformulate a problem in terms of something completely different usually gives you a different perspective and allows you to pull out a different toolbox to attack it. Sometimes, I feel like linear algebra's existential purpose is to serve as a set of easily solved problems into which other, more difficult, problems can be reduced.

In the 9th grade, we were learning about solving systems of linear equations, and there was this one bit on "representing" the equations in a matrix. And that went totally over my head. I was like, there are these stupid equations, what the hell do they have to do with this box of letters? And I didn't get it. It was too hard for me to accept the fact that to solve one problem, it's sufficient to solve a transformation of that problem. Sometimes you get it, sometimes you don't, but understanding the principle of reduction is kinda cool.

Of course, just knowing that reduction is useful doesn't really help much when you're trying to solve a problem... I guess that's what makes some people way better than others at problem solving - being able to spot reductions. All of those stupid tech/finance interview questions asking you about probabilities and numbers and shit like that, they're really just seeing how good you are at reducing an unfamiliar problem to one for which you have a known solution.

I liked the way Feynman described his mathematical skills as nothing but a toolbox... He'd say that what made him good was that he simply had a different toolbox from most other people, and that quite often, his tools fit better than others at solving, say... questions related to theoretical nuclear physics. So that's total bullshit (the part about what made him good), but for some reason, I really liked that portrayal. You see a problem, you turn it around, massage it, and then see what tools you can use to attack it. If it works, great. If not, try again.

---

No comments, be the first!

---

Comments disabled until the spammers go away. I hope you comment spammers all die horrible deaths and are forced to delete endless streams of comment spam in your days in purgatory.