I think there are situations where you can still have subproblems where the output of the subproblem is long. A contrived example: suppose you have a problem where you want to calculate XOR(f(a), f(b)), where f(a) and f(b) are long strings. It seems reasonable to decompose into x=f(a), y=f(b), z=XOR(x, y), despite x and y being long, because there’s a simple way to combine them.
If we had an AI system that could work on “making progress on a problem for an hour”, then write down a complete description of everything it had figured out and pass that to another AI system, I’d count that as dividing the problem into subproblems, just in a way that’s probably inefficient.
I’d evaluate decompositions into subproblems by something like the total cost of solving a problem by dividing it into subproblems. Some decompositions would be efficent and others would be inefficient, sometimes this would be because the output is large but in other cases it could be because it takes a long time to write the input, or because there’s a lot of work repeated between subproblems.
This is really good comment. I’m not sure yet what I think about it, but it’s possible that the post is not quite right. Which might be a big deal because the upcoming sequence relies on it pretty heavily. I take purely abstract examples seriously.
One thing to note, though, is that your counterexample is less of a counterexample than it looks on first glance because while the size of the solutions to [subproblems of your natural decomposition] can be made arbitrarily large, the size of the overall solution grows equally fast.
If we allow two subproblems, then the optimal decomposition (as defined by the post) would be s1=L(f(a))⊗L(f(b)), s2=R(f(a))⊗R(f(b)), where L and R denote the first and second half of a string. Here, the solutions to subproblems are half as long, which is optimal.
These subproblems sound like they’re harder to solve, but that’s not necessarily the case; depends on f. And if they can be solved, it seems like the decomposition would still be preferable.
I think there are situations where you can still have subproblems where the output of the subproblem is long. A contrived example: suppose you have a problem where you want to calculate XOR(f(a), f(b)), where f(a) and f(b) are long strings. It seems reasonable to decompose into x=f(a), y=f(b), z=XOR(x, y), despite x and y being long, because there’s a simple way to combine them.
If we had an AI system that could work on “making progress on a problem for an hour”, then write down a complete description of everything it had figured out and pass that to another AI system, I’d count that as dividing the problem into subproblems, just in a way that’s probably inefficient.
I’d evaluate decompositions into subproblems by something like the total cost of solving a problem by dividing it into subproblems. Some decompositions would be efficent and others would be inefficient, sometimes this would be because the output is large but in other cases it could be because it takes a long time to write the input, or because there’s a lot of work repeated between subproblems.
This is really good comment. I’m not sure yet what I think about it, but it’s possible that the post is not quite right. Which might be a big deal because the upcoming sequence relies on it pretty heavily. I take purely abstract examples seriously.
One thing to note, though, is that your counterexample is less of a counterexample than it looks on first glance because while the size of the solutions to [subproblems of your natural decomposition] can be made arbitrarily large, the size of the overall solution grows equally fast.
If we allow two subproblems, then the optimal decomposition (as defined by the post) would be s1=L(f(a))⊗L(f(b)), s2=R(f(a))⊗R(f(b)), where L and R denote the first and second half of a string. Here, the solutions to subproblems are half as long, which is optimal.
These subproblems sound like they’re harder to solve, but that’s not necessarily the case; depends on f. And if they can be solved, it seems like the decomposition would still be preferable.