Minimising the Number of Multiplications

[jestingrabbit]

I'm looking for an algorithm that will optimally solve the following problem: given a finite set of variables, V = {a, b, c, ... } and a finite set of products of those variables P = {P1, P2, P3, ...}, what is the minimal number of multiplications required to calculate all the elements of P, and what is the algorithm for calculating the elements of P?

So, for instance, if I have V = {a, b, c, d} and P = { abc, abd } then you only need 3 multiplications, one to find A = ab, and one each to find Ac and Ad.

I expect that someone has already done a fair bit of work on this problem, so a few references would be great, though a reasonably efficient algorithm would be better.

[jaap]

I don't have any references for you, but I suspect it is an NP-complete problem. If your products allow variables to be repeated, then it definitely is because exponentiation with minimal multiplications is already NP-complete. See for example this wiki page.

[Ankit1010]

I think the algorithmic time will be exponential unless |P| grows exponentially to |V|.
The number of terms in the final answer will grow proportionally to 2^n, and if |P| does not grow exponentially to |V|, the number of multiplications required will overall grow exponentially.

[shawnhcorey]

It seems to me that all you need do is modify the find-all-subsets routine to create, store and reuse the partial products as the subset is being generated. Not that hard. Since finding all subsets is a NP problem, this would be too.

[Jplus]

Perhaps not a complete solution, but you might want to have a look into frequent itemset mining.

[jestingrabbit]

I don't have any references for you, but I suspect it is an NP-complete problem. If your products allow variables to be repeated, then it definitely is because exponentiation with minimal multiplications is already NP-complete. See for example this wiki page.

That WP page is a pretty good one. Section 6 of the below pdf seems to be what I'm after, though I haven't checked all the details yet.

http://cr.yp.to/papers/pippenger.pdf

Thanks.

[jestingrabbit]

I thought I'd add an ending to the story, because it ended pretty well. The actual products that I had to calculate were of n+2 things each, and there were n+1 of them, so naively it would have cost (n+1)^2 multiplications. In the end though, using some cunning, I go it down to an upper bound of 9n/2.

So, optimisation dreams do happen!