ADDITIVE COMPLEXITY IN DIRECTED COMPUTATIONS

Abstract. A straight-line additive computation which computes a set SZ of linear forms can be presented as a product of elementary matrices (one instruction of such a computation corresponds to a multiplication by an elementary matrix). For the general complexity measure no methods for obtaining nonlinear lower z?ounds for concrete natural sets of linear forms are known at the moment (under the general cchmplexity measure of & we mean the minimal number of multipliers in products computing JzZ). In the paper threz complexity measures (triangular, directed and a modification of the latter-reduced directed complexity) close in spirit each to others are defined and investigated. For these measures ome ncjnlinear lower bounds are obtained. Moreover, the.problem of the exact explicit calculation of the directed complexity is solved for which a suitable algebraic apparatus (the generalized Bruhat decomposition) is developed. Apparatus is exposed in the appendix to the paper. 1. Introduction and basic: notions Development of methods for obtaining nonlinear lower bounds in the algebraic computational complexity still remains an unsolved problem for the present. In the paper two models of computation (triangular and directed) are introduced, and nonlinear lower bounds of complexity are obtained for these models. Connections o