On parallel evaluation of certain classes of polynomials with an increasing number of variables (Q804282)

In this paper we shall evaluate polynomials with integral coefficients by formulas in the basis \(B=\{xy,x\pm y,1\}\). We introduce the concept of a formula by induction as follows. (1) A formula of depth 1 and complexity 1 is a symbol of variables or is a basis constant equal to 1. (2) If \(\Phi_ 1\) and \(\Phi_ 2\) are two formulas of depth \(D_ 1\) and \(D_ 2\) and of complexity \(L_ 1\) and \(L_ 2\), respectively, then \((\Phi_ 1\circ \Phi_ 2)\) is a formula of depth \([1+\max (D_ 1,D_ 2)]\) and complexity \([L_ 1+L_ 2+1]\), where the symbol \(\circ\) stands for multiplication, addition or substraction \((\cdot,+,-).\) Let L(f) and D(f) denote the minimal complexity and minimal depth of formulas realizing a polynomial f. The depth D(f) can be interpreted as the time required to compute the polynomial f by an indefinite number of processors which execute arithmetic operations over natural numbers (under the assumption that computation time does not depend on the operation type and magnitude of the operands). Consider the class \({\mathcal P}_ c(d)\) consisting of all polynomials with coefficients 0,1,...,c and of degrees \(d_ i\) in the variables \(x_ i\), where \(d=(d_ 1,d_ 2,...d_ n)\). Let us put L(\({\mathcal P}_ c(d))=\max \{L(f):\) \(f\in {\mathfrak P}_ c(d)\}\), D(\({\mathcal P}_ c(d))=\max \{D(f):f\in {\mathcal P}_ c(d)\}.\) Then the following assertion holds: Let n tend to infinity. Then L(\({\mathcal P}_ c(d))\sim H/\log_ 2n\) and for \(d_ 1+...+d_ n+\log c=2^{O(n/\log n)},\) the following equality holds: \[ D({\mathcal P}_ 1(d))=\log_ 2H-\log_ 2\log_ 2n+O(1), \] where \(H=(d_ 1+1)...(d_ n+1)\log (c+1)\).