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.
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.