Test complexity of generic polynomials (Q1201154)

A classical problem in algebraic complexity is to find lower bounds for polynomial evaluation, i.e. for the problem of evaluating a complex polynomial \(f\in C[x_ 1,\ldots,x_ m]\) at a point \(\xi\in C^ m\). Given \(f\in C[x_ 1,\ldots,x_ m]\), one says that an algebraic computation tree \(T\) computes \(f\) when for every \(\xi\in C^ m\) the output of \(T\) with input \(\xi\) is \(f(\xi)\). The complexity of polynomial evaluation for a given \(f\) is the minimal depth of all algebraic decision trees that compute \(f\). Additive (or multiplicative) complexity is defined in the same way but counting only additions and substractions (resp. nonscalar multiplications or divisions) when considering the depth of the computation tree. Many results have been provided in the last decades that show lower bounds for this problem that depend on \(f\). In particular, the case of polynomials having coefficients that are algebraically independent over \(\mathbb{Q} \) has been largely studied and for this case the following bounds hold \begin{align*} L_+(f)&\geq \binom{d+m}{m}-1,\\ L_*(f)&\geq \biggl[ \binom{d+m}{m}-1\biggr]/2, \end{align*} where \(L_ +(f)\) is the additive complexity of \(f\) and \(L_ *(f)\) its multiplicative complexity. More recently, attention has been paid to an \textit{a priori} simpler problem, to decide just whether \(f(\xi)\) equals zero. The main result of the reviewed paper is that for the case of algebraically independent coefficients testing for zero is not easier than evaluating at a point. In fact, the authors consider a hypersurface \(X\subset C^ m\) having irreducible components \(X_ 1,\ldots,X_ t\) satisfying \begin{align*} &X_i=\text{Zeroset}(f_i), \quad f_i\in C[x_1,\ldots,x_m]\text{ irreducible}\\ &\deg(f_i)=d_i\quad (i=1,\ldots,t) \end{align*} such that the polynomials \(f_ 1,\ldots,f_ t\) can be chosen such that all their coefficients are algebraically independent over \(\mathbb{Q} \), and they derive the bounds \begin{align*} C_{+,=}(X)&= \sum_{i=1}^t\biggl[\binom{d_i+m}{m}- 1\biggr],\\ C_{*,=}(X)&\geq \frac12 \sum_{i=1}^t \biggl[ \binom{d_i+m}{m}-1\biggr], \end{align*} where \(C_{+,=}\) denotes the branching additive complexity (we now count additions, substractions and equality tests) and \(C_{*,=}\) the multiplicative branching complexity (i.e. the minimal number of nonscalar multiplications, divisions and equality tests). Moreover, they show that the second bound is sharp for min\(_{1\leq i\leq t} d_ i\to\infty\) keeping \(m\) and \(t\) fixed. A related problem is posed in a natural way when considering real varieties instead of complex ones. For this case the authors show that the same bounds hold for irreducible varieties. In fact, for \begin{align*} &X=\text{Zeroset}(f), \quad f\in\mathbb{R}[x_1,\ldots,x_m]\text{ irreducible}\quad \deg(f)=d\\ \end{align*} with the coefficients of \(f\) algebraically independent over \(\mathbb{Q}\) the following bounds hold \begin{align*} C_{+,\leq}(X)&=\binom{d+m}{m}-1,\\ C_{*,\leq}(X)&\geq \frac12 \biggl[ \binom{d+m}{m}-1\biggr], \end{align*} where we note that we allow inequality tests of the form \(y\geq 0\) in the decision trees and these tests are now considered for computing the additive and multiplicative branching complexities. A final result shows that the irreducibility hypothesis is a necessary assumption since for the reducible zero-dimensional case, both additive and multiplicative complexities turn out to be logarithmic in \(t\) (the number of points).