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.

## Minimising the Number of Multiplications

**Moderators:** phlip, Moderators General, Prelates

- jestingrabbit
- Factoids are just Datas that haven't grown up yet
**Posts:**5967**Joined:**Tue Nov 28, 2006 9:50 pm UTC**Location:**Sydney

### Minimising the Number of Multiplications

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

### Re: Minimising the Number of Multiplications

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.

### Re: Minimising the Number of Multiplications

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.

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
**Posts:**42**Joined:**Sun Jan 08, 2012 2:08 pm UTC

### Re: Minimising the Number of Multiplications

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.

### Re: Minimising the Number of Multiplications

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

"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

coding and xkcd combined

(Julian/Julian's)

- jestingrabbit
- Factoids are just Datas that haven't grown up yet
**Posts:**5967**Joined:**Tue Nov 28, 2006 9:50 pm UTC**Location:**Sydney

### Re: Minimising the Number of Multiplications

jaap wrote: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.

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

- jestingrabbit
- Factoids are just Datas that haven't grown up yet
**Posts:**5967**Joined:**Tue Nov 28, 2006 9:50 pm UTC**Location:**Sydney

### Re: Minimising the Number of Multiplications

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!

So, optimisation dreams do happen!

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

### Who is online

Users browsing this forum: No registered users and 6 guests