# Do you know of a brute-force algorithm for optimizing polynomial expressions? [closed]

For instance, given the polynomial expression $xy + x + y + 1$ it will output $(x+1)(y+1)$.

Thanks!

• You mean factorization, right? Apr 21 '14 at 6:11

## 1 Answer

"Brute-force" in the context of factoring polynomials may involve factoring of integers, which is a hard problem. Factoring polynomials is easier, e.g. look up "FACTORING MULTIVARIATE POLYNOMIALS VIA PARTIAL DIFFERENTIAL EQUATIONS" by Gao, and "Factoring Multivariate polynomials over the integers" by Wang and Rothschild.

• Are you saying that since you can represent integers with polynomials, for instance $1 + X + X^2$ to represent $7$ (in binary), that finding the optimal polynomial would be a superset of the problem of integer factoring? Apr 21 '14 at 18:12
• @EnjoysMath No I'm saying the opposite, I'm saying that finding a polynomial factorization (or determining that a polynomial is irreducible) is easier than factoring an integer or determining that it's prime. Just because a polynomial is irreducible doesn't mean the polynomial always produces prime values, and just because an integer is not prime doesn't mean it will be easy to find a non-trivial polynomial that the integer satisfies that can be factored. Apr 21 '14 at 18:16