Consider signed integers with common addition and multiplication.

Reassociation of expression is another equivalent form.

Say expressions:

a * b + a * c + c * b
a * (b + c) + c * b
a * b + c * (a + b)

Are all reassociations of each other.

Lets call optimal reassociation one with minimal multiplications.

It can be hard to observe. For instance:

a * c - a * d - b * c - e * f + e * d + b * f

Optimal reassociation is tricky:

(a - b) * (c - d) - (e - b) * (f - d)

To build this one we need to guess utterly non-obvious step: add and subtract b * d to original one.

Yes/No problem may be stated like this: I give you expression E which is sum of monomials and number N, you shall answer if there exists reassociation of E with no more than N multiplications.

I believe this is no harder than NP: if oracle gives us simplified expression it takes polynomial time to simplify braces and check answer against E.

My question is: if this problem NP-complete and how can I prove this? Or is there some smart polynomial algorithm?

  • $\begingroup$ Can you elaborate on how to verify a given expression E is equivalent to a certificate expression C (the simplified expression) in time that is polynomial in E? Keep in mind that the expansion of E and C (applying the distributive property on all brackets) in order to end with an expression that is a sum of monomials might be non-polynomial. Or are you considering the problem where E is given in the form of a sum of monomials (with no brackets)? $\endgroup$ Commented Oct 3, 2023 at 10:03
  • $\begingroup$ Also, observe that above $\mathbb{F}_2$ that problem is at least coNP-complete. One may transform a CNF formula $\phi$ into an expression that is equivalent to 0 as a polynomial above $\mathbb{F}_2$ iff $\phi$ is un-sat. $\endgroup$ Commented Oct 3, 2023 at 10:09
  • $\begingroup$ Yep, E is given in the form of a sum of monomials $\endgroup$ Commented Oct 4, 2023 at 5:49


Your Answer

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