I see the main contribution/idea of this post as being: whenever you make a choice of basis/sorting-algorithm/etc, you incur no “true complexity” cost if any such choice would do.
I would guess that this is not already in the water supply, but I haven’t had the required exposure to the field to know one way or other. Is this more specific point also unoriginal in your view?
I think this point is obvious, but I don’t really remember what points were obvious when I took algorithmic info theory (with one of the people who is most likely to have thought of this point) vs what points I’ve learned since then (including spending a reasonable amount of time talking to Soares about this kind of thing).
I see the main contribution/idea of this post as being: whenever you make a choice of basis/sorting-algorithm/etc, you incur no “true complexity” cost if any such choice would do.
I would guess that this is not already in the water supply, but I haven’t had the required exposure to the field to know one way or other. Is this more specific point also unoriginal in your view?
I think this point is obvious, but I don’t really remember what points were obvious when I took algorithmic info theory (with one of the people who is most likely to have thought of this point) vs what points I’ve learned since then (including spending a reasonable amount of time talking to Soares about this kind of thing).