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?

  • $\begingroup$ 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? $\endgroup$ – Algeboy Sep 20 '18 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.