# 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

## 1 Answer

Since you said my comment answered your question, I'm turning it into an answer so the question can be marked as answered:

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

(By the way, under this interpretation of the question, presumably the coefficients of the polynomials are considered to be taken from some (relatively simple) subset of the possible values of the indeterminates? Else it wouldn't make sense to have scalar multiplication cost 0 and indeterminate multiplication cost 1, since they'd be the same operation.)

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 23, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9522695541381836, "perplexity_flag": "head"}