There is no requirement, either explicit or implicit, that S_1 or S_2 be small relative to the data. Either or both could be e.g. a third the size of the data, or almost as large as the data itself.
I was thinking of “small” in terms of K-complexity, but I had still misunderstood it. Is the rough intuition behind this result the following:
Suppose has two components, which generates , and which generates the data given . We can “combine” and to form a program which first uses to generate and then uses to generate given . Then either and have some shared structure, in which case so is shorter than or and have no shared structure, in which so is shorter either than or . Or some combination of the two.
There is no requirement, either explicit or implicit, that S_1 or S_2 be small relative to the data. Either or both could be e.g. a third the size of the data, or almost as large as the data itself.
I was thinking of “small” in terms of K-complexity, but I had still misunderstood it. Is the rough intuition behind this result the following:
Suppose