Is there an efficient algorithm to reduce the degree of a multivariate polynomial given a list of monomial substitutions?

Question

The degree of an $n$-variate polynomial is defined as the maximum degree of the monomials that composes it. Now, given a polynomial $P$ (or rather, a list of monomials, since the coefficients don't matter here) and a list of monomial substitutions, is there an efficient algorithm that is guaranteed to find a sequence of substitutions that minimize the degree of the resulting polynomial?

A substitution is to be seen as an equality. That is, the substitution $X_1X_2\to X_3$ can be read as $X_1X_2=X_3$. We are thus free to replace one by the other independently on each monomial that compose te polynomial if that is convenient. For instance, the polynomial $X_1^2X_2+X_1X_2^3+X_3^3$ can well be transformed using the single substitution rule $X_1X_2\to X_3$ into $X_1X_3+X_1X_2^3+X_3^3$ (substitution on the first monomial) or into $X_1X_2^2+X_1X_2^3+X_1^3X_2^3$ (substitution on the first monomial and the third one), etc.

Note that (if I'm not mistaken), we can always assume that substitutions will not lead to simplifications, in the sense that we'll never be able to remove a monomial by doing a substitution (for instance, that would be the case if we were to start from $X_1X_2-X_3$ with the substitution rule $X_1X_2\to X_3$). The reason why we can afford to assume this is that simplifications can only occur when transforming a monomial into one that is already present in the summation. But in that case, subsequent steps will simplify the monomials in the same way so that they stay equal, and we'll be able to simplify the polynomial at the very end. To be fair, it may matter when trying to minimize the degree of the polynomial, especially if the terms that we remove are the highest degree ones, but I think that for simplicity, it's for now better to assume that it won't be possible.

I can't really wrap my head around it because applying substitutions in different order may lead to different results. For instance, consider the polynomial $$P=X_0^3X_1$$ with the substitutions $X_0^3\to X_1$, $X_0^2X_1\to X_2^2$ and $X_0X_2\to 1$. We can either apply the first or the second substitution. In the first case, we get $$X_0^3X_1\to X_1^2$$ from which we can't apply any other substitutions. But if we start with the second rule: $$X_0^3X_1\to X_0X_2^2\to X_2$$ and we end up with a polynomial of smaller degree. So, the order in which we apply the substitutions matter, and greedy algorithms are not guaranteed to give the optimal solution for this problem.

I think any algorithm that wishes to do so is basically forced to run a routine that will run on each monomial in the polynomial, and then select the one that overall leads to the smallest degree. So, the problem can be equivalently restated with $P$ being a monomial.

Apart from that, I don't really see any smart ideas about doing this, even if I assume that the substitutions always preserve or lower the degree of a monomial.

If I represent the starting monomial with the root of a tree, then I can just build a tree with each branch representing one substitution, but that may grow very quickly with the number of substitutions, and adding an assumption like the aforementioned one on the degrees being lowered doesn't really seem to help (though it shows that the tree stops growing at some point).

Is there a nicer way to do it?

---

Another way to state this problem (at least in the case where we want to reduce a monomial, which I conjecture is the most efficient way to then reduce a polynomial) is the following: you're given a vector $x\in\mathbb{N}^n$ and a finite list of pairs $\left\{(a_i, b_i)\right\}_i$ with $a_i$ and $b_i$ being also elements of $\mathbb{N}^n$.

Starting from $x$, you are allowed to replace $x$ by $x-a_i+b_i$ for any $i$ of your choice (where $+$ and $-$ are the common addition and subtraction on vectors), but you can do so only if $x-a_i\in\mathbb{N}^n$ (that is, each coefficient of $a_i$ is less than the associated coefficient of $x$). You can then repeat this process, with the set of allowed modifications remaining the same, and the new starting point being $x-a_i+b_i$. The algorithm terminates when no substitution can be applied anymore.

The goal of the algorithm is to minimize the sum of coefficients of the final vector.

---

I care about this problem from a practical perspective, where the number of variables $n$ is in the order of magnitude of 10ドル$, the number of monomials grows as $n!$, the number of substitutions is in the order of $n$, the maximal degree of the starting polynomial is in the order of magnitude of 10ドル$ and the degree of the substitutions is generally fairly low, say no more than 4ドル$.

• D.W.: Possibly related (I haven't checked): cs.stackexchange.com/q/142152/755, cs.stackexchange.com/q/125011/755, cs.stackexchange.com/q/142148/755, cs.stackexchange.com/q/161940/755, cs.stackexchange.com/q/57957/755
• Tristan Nemoz: @D.W. I've edited the post with the relevant information. Thanks for the links, I'll take a look!
• D.W.: Can you specify the effect of applying a substitution to a polynomial? I don't see that defined anywhere, I only see examples. For instance: if $p$ contains multiple monomials, can I choose to apply the substitution to some of the monomials and not others, or must I apply it to all? What if the preconditions for the substitution are satisfied for some of the monomials and not others; what is the effect? Can I still apply the substitution, and then what will the resulting polynomial be? (e.g., $P=X_1^2X_2 + X_1 X_2^3 + X_3^3$ with substitution $X_1 X_2 \to X_3$?)
• Tristan Nemoz: @D.W. I've added more explanation on this, please tell me if that's not clear enough!