Is it possible to compute the Kolmogorov complexity of a polynomial over ℚ?

For the sake of making the above well-defined, let's suppose our description language is arithmetic expressions in Polish notation with symbols 0 1 x + - * / ^. If there is some other description language you find easier to reason about, though, then feel free to use that one; I'm not too fussed as long as it captures some reasonable notion of complexity.

Is there a method by which a function given by a polynomial with coefficients in ℚ can be algorithmically reduced to its shortest description in that language?

• Horner's rule would give you the formula with the least products, which would be one measure of the complexity. Are you also costing the complexity to encode rationals? Or are they unit cost? – Algeboy Sep 20 '18 at 1:13