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).