Verification complexity of linear prime ideals (Q1207526)

The paper describes the complexity of algebraic decision trees deciding membership in an algebraic subset \(X\subseteq R^ m\) where \(R\) is a real or algebraically closed field. The authors define a notion of verification complexity of a prime ideal which gives a lower bound on the decision complexity. They determine the verification complexity of some prime ideals of linear type generalized a result by \textit{S. Winograd} [On the number of multiplications necessary to compute certain functions, Commun. Pure Appl. Math. 23, 165-179 (1970; Zbl 0191.158)]. As an application they show uniform optimality with respect to the number of multiplications and dimensions needed for two algorithms. The paper is organized as follows: Section 1 summarizes some known results. Section 2 recalls some notions from real algebraic geometry. Sections 3 and 4 introduce terminology based on these notions and contains definitions from algebraic complexity theory. In Section 3 the authors give a definition of verification complexity of prime ideals, and in Section 4 they show that this notion gives lower bounds on decision complexity. Section 5 contains a lower bound result for verification complexity of prime ideals of a linear type which is applied in Section 6 to the membership problem of the zerosets of polynomials in (1) or (2).