Effective transformations are uncommon, but when one is possible and you find it, you win. Transformation can’t really deal with inherently hard problems, but it can show you that a problem you thought was hard is actually easy if you look at it in an alien way.
I can think of another example, but unfortunately it’s even more technical. (Not all hard problems are as easy to state as the Four Color Theorem! But like the BWT, this one directly affects the real world.) C++ programmers have been dealing with a hard problem for decades—the language allows high abstraction to coexist with high performance, but it’s a little too fond of copying memory around. This takes time (i.e. decreases performance) for no useful benefit. Recently, scary wizards discovered that the problem of identifying which copies are necessary and which are not can be transformed into the problem of distinguishing lvalues from rvalues (insert animal noises here if you like—this is the technical part). Before this discovery, the language didn’t allow programmers to cleanly distinguish between meows and woofs (so knowing this wouldn’t have helped ordinary programmers). But compilers have always been able to distinguish between them. It’s like Compilers 101, and even C compilers know the difference. Exposing this bit of information to user-programmers in a certain way allows all of those nasty unnecessary copies to be avoided. Someone directly attacking the problem of unnecessary copies would never have invented this in two to the twentieth years.
As a bonus, this solved many hard problems at once—it turns out that once user-programmers can tell meows and woofs apart, they can also solve the “forwarding problem” with “perfect forwarding”, making Boost’s developers (and me) cry with joy.
To restate, finding an appropriate transformation is a trick that turns a hard problem that you can’t directly attack, into an easy problem that you already know how to solve, or can figure out how to solve without very much work. It doesn’t solve the problem by itself, but it feels like it does. I would expect most if not all examples to be in mathematics and the hard sciences where abstractions can be cleanly and rigorously transformed, but I would be pleasantly surprised by an example from biology, etc.
This C++0x feature is rvalue references. Wikipedia has an article section about it, although it contains inaccuracies (“The function returning a std::vector temporary need only return a std::vector&&.” is wrongity wrong.)
Why? (I’m genuinely curious. I haven’t yet figured out how being on Facebook could be a productive use of my free time, which is unfortunately very limited.)
I’m genuinely curious. I haven’t yet figured out how being on Facebook could be a productive use of my free time, which is unfortunately very limited.
The basic functionality is simply to keep track of the list of interesting people, ideally with contact info automagically updating. Following the status updates is an extra that supports the sense of being in touch without explicit effort on your part, which can be made efficient if you block enough of the more prolific/uninteresting updates, and/or restrict the connections to people you know reasonably well.
A perhaps similar example, sometimes I have solved geometry problems (on tests) by using analytical geometry. Transform the problem into algebra by letting point 1 be (x1,y1), point 2 be (x2,y2), etc, get equations for the lines between the points, calculate their points of intersection, and so on. Sometimes this gives the answer with just mechanical application of algebra, no real insight or pattern recognition needed.
many important arbitrarily complicated functions can be represented as sums of much simpler functions
Check out Integral transforms, there’s a huge class of transforms that solve a bunch of math problems handily, and it comes with that nice explanation of why they seem to work so often.
The trick consists on discovering a twist you can apply to your complicated object which makes it easily separable into pieces that are susceptible to the function you wanted to apply to your object, such that you have some way of also untwisting your function’d twisted object to get your answer.
Here’s an example of Tim Gowers trying to apply the trick to help solve the Erdos Discrepancy Problem, subject of Polymath5 (collaborative mathematics over the internet!). That’s less than 24 hours ago. Yeah, it’s that useful in mathematics. :D (Edit: looking at it again, I’d say it’s a combination of transform and meta, which is a common combo)
This is interesting, but I find it specific enough that I think I’d have trouble applying it to another domain.
Less Wrong comments use (a not completely bug-free implementation of) Markdown.
Four spaces worked! Thank you.
Effective transformations are uncommon, but when one is possible and you find it, you win. Transformation can’t really deal with inherently hard problems, but it can show you that a problem you thought was hard is actually easy if you look at it in an alien way.
I can think of another example, but unfortunately it’s even more technical. (Not all hard problems are as easy to state as the Four Color Theorem! But like the BWT, this one directly affects the real world.) C++ programmers have been dealing with a hard problem for decades—the language allows high abstraction to coexist with high performance, but it’s a little too fond of copying memory around. This takes time (i.e. decreases performance) for no useful benefit. Recently, scary wizards discovered that the problem of identifying which copies are necessary and which are not can be transformed into the problem of distinguishing lvalues from rvalues (insert animal noises here if you like—this is the technical part). Before this discovery, the language didn’t allow programmers to cleanly distinguish between meows and woofs (so knowing this wouldn’t have helped ordinary programmers). But compilers have always been able to distinguish between them. It’s like Compilers 101, and even C compilers know the difference. Exposing this bit of information to user-programmers in a certain way allows all of those nasty unnecessary copies to be avoided. Someone directly attacking the problem of unnecessary copies would never have invented this in two to the twentieth years.
As a bonus, this solved many hard problems at once—it turns out that once user-programmers can tell meows and woofs apart, they can also solve the “forwarding problem” with “perfect forwarding”, making Boost’s developers (and me) cry with joy.
To restate, finding an appropriate transformation is a trick that turns a hard problem that you can’t directly attack, into an easy problem that you already know how to solve, or can figure out how to solve without very much work. It doesn’t solve the problem by itself, but it feels like it does. I would expect most if not all examples to be in mathematics and the hard sciences where abstractions can be cleanly and rigorously transformed, but I would be pleasantly surprised by an example from biology, etc.
(Edit: Avoided unnecessary sentence.)
As a former C++ programmer who doesn’t keep track of the current events, I’d appreciate a specific link/keyword to the mechanism you were describing.
This C++0x feature is rvalue references. Wikipedia has an article section about it, although it contains inaccuracies (“The function returning a std::vector temporary need only return a std::vector&&.” is wrongity wrong.)
Pleased to make an acquaintance of your secret identity. :-) It’s a shame you are not on Facebook.
Why? (I’m genuinely curious. I haven’t yet figured out how being on Facebook could be a productive use of my free time, which is unfortunately very limited.)
The basic functionality is simply to keep track of the list of interesting people, ideally with contact info automagically updating. Following the status updates is an extra that supports the sense of being in touch without explicit effort on your part, which can be made efficient if you block enough of the more prolific/uninteresting updates, and/or restrict the connections to people you know reasonably well.
Would upvote again if I could. Please consider this as encouragement to post more.
Thanks; I’ll try to write a full post one of these days.
A perhaps similar example, sometimes I have solved geometry problems (on tests) by using analytical geometry. Transform the problem into algebra by letting point 1 be (x1,y1), point 2 be (x2,y2), etc, get equations for the lines between the points, calculate their points of intersection, and so on. Sometimes this gives the answer with just mechanical application of algebra, no real insight or pattern recognition needed.
When I was a kid this was how I solved all nontrivial geometry problems, because I was much better at algebra than geometry!
Check out Integral transforms, there’s a huge class of transforms that solve a bunch of math problems handily, and it comes with that nice explanation of why they seem to work so often.
The trick consists on discovering a twist you can apply to your complicated object which makes it easily separable into pieces that are susceptible to the function you wanted to apply to your object, such that you have some way of also untwisting your function’d twisted object to get your answer.
Here’s an example of Tim Gowers trying to apply the trick to help solve the Erdos Discrepancy Problem, subject of Polymath5 (collaborative mathematics over the internet!). That’s less than 24 hours ago. Yeah, it’s that useful in mathematics. :D (Edit: looking at it again, I’d say it’s a combination of transform and meta, which is a common combo)
Let’s try applying that to a recent hard problem: The Preference Utilitarian’s Time Inconsistency. (...time passes...) Didn’t see a way. How about a reference class that says “cryonics, singularity, superhuman AI etc. are highly probable”?
Here’s my attempt.