# Ambiguity in computing straight-line complexity of multivariate polynomials

I was wondering:

I'm desiring to compute the following polynomial, $X_1^2 + 2 X_1\cdot X_2 +X_2^2$ where $X_1,X_2$ are indeterminates. I can store intermediate results and use the binary operators of multiplication and addition on the indeterminates.

If the cost of taking a scalar multiple is $0$, and the cost of using addition and multiplication is $1$, then consider the following:

Let $P=X_1+X_2$ (cost $1$). Let $Q=P \cdot P$ (cost $1$).

Now at this point $Q$ is $(X1+X2) \cdot (X1+X2)$. Am I allowed to be done with the computation at this point? Or must I end with the explicit $X_1^2+ 2 X1 \cdot X2 +X_2^2$ in order to have computed $X_1^2+2X_1 \cdot X_2+ X_2^2$? (Which would take $5$ steps).

-
I don't understand. You say you can use multiplication and addition "on the indeterminates". a) I'm not sure what that means, and b) in $Q=P\cdot P$ you're using multiplication on "$P$", by which you may be denoting either the result of performing $X_1+X_2$ or the polynomial $X_1+X_2$, neither of which is an indeterminate. The only way I can make sense of the first part of the question is if you in fact mean that you can perform multiplication and addition on the values taken by the indeterminates; but in that case $(X_1+X_2)\cdot(X_1+X_2)$ is the same as $X_1^2+2X_1\cdot X_2+X_2^2$. – joriki Aug 23 '11 at 5:58
Sorry, I was a bit tired last night and couldn't find the answer to this anywhere. Anyways yes, I mean you can perform multiplication and addition on the values taken on by the indeterminates. And you answered my question. Thanks! – seagaia Aug 23 '11 at 13:13

If multiplication and addition refer to the values taken by the indeterminates, then $(X_1+X_2)\cdot(X_1+X_2)$ is the same as $X_1^2+2X_1\cdot X_2+X_2^2$, so there's nothing left to do; the computation was carried out efficiently with cost $2$ instead of cost $5$.