Let's say that I have a multi-variate arithmetical expression $A(x_1, \ldots, x_n)$ that uses addition and multiplication operations and is also in a very simple form of sums of products, e.g., $A_1(x_1, x_2) = x_1\cdot x_1 + x_1\cdot x_2$.

Let's also say that the size of an expression is the number of addition/multiplication operators that appear in that expression. For example, size of $A_1(x_1, x_2)$ is three.

Now, I want to find another expression (also only using addition and/or multiplication) that is equivalent to the given expression $A$ and is of the minimum size. For example, formula $A_2(x_1, x_2) = x_1\cdot(x_1+x_2)$ of size two would be the answer to input $A_1$.

My question is about the complexity of finding $A_2$ from $A_1$. The decision version of this problem (does there exist such $A_2$ of size at most $k$) is obviously in NP but is it NP-complete?

If yes, then do we have any good approximation algorithm for it? Or other heuristic algorithms?

If not, what is the best known algorithm to solve it?

  • $\begingroup$ seems to be nearly the same as MCSP, minimum circuit size problem (with restricted gates), see eg rjlipton. also close to arithmetic circuit complexity theory. also similar to polynomial identity testing. $\endgroup$ – vzn Feb 4 '16 at 16:12

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.