2
$\begingroup$

Sometimes an ugly polynomial (perhaps in several variables) can be expressed as a small sum of much simpler polynomials. Can this be done algorithmically? More precisely:

Is there a reasonable definition of 'typographical complexity' (minimal space needed for the definition of a polynomial) and an algorithm transforming an expression for an arbitrary polynomial $P$ into an expression close to the minimal typographical complexity of $P$?

Such an algorithm would be useful for shortening papers full of complicated polynomials or perhaps for storing a huge number of polynomials.

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ This is called arithmetic circuit complexity, there is a lot of research around it, and no, in general it is computationally hard to simplify a given expression to an optimal (or close to optimal) expression. $\endgroup$
    – Emil Jeřábek
    Feb 16, 2022 at 18:00
  • 2
    $\begingroup$ It is perhaps worth mentioning the problem for the setting of boolean circuits is well-known/studied (by the name of the Minimum Circuit Size Problem). It has a very interesting history, and is probably the most obvious candidate for an NP hard problem whos hardness is unknown (trying to prove hardness of MCSP delayed Levin's paper on NP completeness iirc). There are a number of breakthroughs in recent years, see Allender's survey. Again, this is the boolean case, so this is solely a comment rather than an answer, but in the boolean case ... $\endgroup$
    – Mark Schultz-Wu
    Feb 16, 2022 at 20:31
  • 2
    $\begingroup$ the hardness of the problem is much more involved than other well-known problems a la 3SAT. $\endgroup$
    – Mark Schultz-Wu
    Feb 16, 2022 at 20:32

1 Answer 1

Reset to default
1
$\begingroup$

There is a trivial algorithm for simplifying a polynomial expression $p$: Consider all polynomials less complex than $p$ using only the variables in $p$, only exponents of at most $\deg(p)$, and whose height is at most the height of $p$.

There are only finitely many of these polynomials, so test if any of them are equal to $p$ by expanding them into sums of monomials, and choose the simplest one equal to $p$.

I don’t know any theory here about efficient algorithms, but Mathematica’s Simplify works pretty well, and uses LeafCount as its measure of complexity.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ I would not call this an algorithm: There is also a perfectly good algorithm for factoring integers: try all possible factorisations! $\endgroup$
    – Roland Bacher
    Feb 16, 2022 at 18:02
  • $\begingroup$ In that case, it would help for the post to specify the desired type of algorithm more closely -- a polynomial-time algorithm, perhaps? $\endgroup$
    – user44143
    Feb 16, 2022 at 18:10
  • 1
    $\begingroup$ If your measure of complexity is the leaf count then there are infinitely many polynomials at any given level of complexity, so exhaustively testing them doesn't really constitute an algorithm. $\endgroup$
    – Peter Taylor
    Feb 16, 2022 at 18:58
  • $\begingroup$ There is (in my opinion) some implicit requirement of usefulness and effectivity in the definition of an algorithm. Otherwise, there is an algorithm for solving every solvable problem: Try all strings of length $n$, $n+1$ and so on. $\endgroup$
    – Roland Bacher
    Feb 16, 2022 at 19:05
  • $\begingroup$ @PeterTaylor, thanks, I fixed this. $\endgroup$
    – user44143
    Feb 16, 2022 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.