# Algorithm to find the minimal number of multiplications

Start with the $$\mathbb{Q}$$-vector subspace $$V_0$$ of the polynomial ring $$Q[x_1,\ldots,x_n]$$ spanned by $$\{1,x_1,\ldots,x_n\}$$. In each step, we can choose an element of the form $$v_iv_i'$$ for $$v_i,v_i'\in V_i$$, adjoin it to $$V_{i}$$ to obtain $$V_{i+1}$$.

Is there an algorithm that computes for a given finite subset $$S$$ the minimal number $$n$$ of steps needed such that there is a choice of $$V_1,\ldots,V_n$$ with $$S\subset V_n$$?

For example $$S=\{x^2+x+1\}$$ can be obtained in one step, use the trick $$x^2+x+1 = x(x+1)+1$$.

Another interesting example is Strassen's algorithm, which says in this language that the entries of a 2x2 matrix multiplication can be obtained in 7 steps, instead of the obvious 8 steps.

After reading this question, I would be surprised if such an algorithm is known in the generality I was asking for.