I'm interested in applications of optimal programs that convert one formal language into another (in particular Python to C++) so this seems highly related. I am thinking along the lines of "how do you generalize / extend" some function. Say the function simply replaces each letter in the string with another string, then it's by definition a monoid homomorphism and extends easily to any string over the same alphabet, or even extended alphabet and acting on added letters as identity. But I also thought, what about permutations. What if the "best" mapping between an input string and an output string is just a permutation of its letters. I also thought that once I figure out a good theory, these programs are "composable" in the sense that you can substitute a variable for a string in the input language (a new/unused variable), and this gives you a new string to operate on; after which you perform the inverse variable substitution to reach the final result. Stuff like that is occupying me all of today and previously has occupied my mind for days at a time for a total of about 30 times, but it's taken various algorithms / forms.
So my question is related to the above thoughts. And it's: do we know of any classes of functions between strings such that the "Kolmogorov-optimal [insert programming language] program" is computable in polynomial time?
For example: $f(x) = x = \text{identity}$. Clearly it is its own Kolmogorov-optimal function for any space pretty much. Then take an "atomic constant" function, meaning it only outputs one letter. Clearly in any reasonable theory we'd define that as optimal of itself as well. Does there exist some algebraic structure not of the optimal programs themselves, but of programs for which a Kolmogorov-optimal solution can be computed in polynomial time? Because it's as if you could easily have a subring or ideal of polynomials that are easy enough to do that for, but most-likely it's going to be a multiplicative monoid intuitively speaking. In other words, its elements are not "optimal", but they do have an easily computable optimal standard form.
Rules: no probablistic algorithm: it has to be deterministic, which it usually is unless you're approximating an optimal solution, which we are not.
