Verification Complexity of Linear Prime Ideals
Title | Verification Complexity of Linear Prime Ideals |
Publication Type | Technical Report |
Year of Publication | 1991 |
Authors | Bürgisser, P., & Lickteig T. Michael |
Other Numbers | 669 |
Abstract | The topic of this paper is the complexity of algebraic decision trees deciding membership in an algebraic subset X propersubset (R superscript m) where R is a real or algebraically closed field). We define a notion of verification complexity of a (real) prime ideal (in a prime cone) which gives a lower bound on the decision complexity. We exactly determine the verification complexity of some prime ideals of lineary type generalizing a result by Winograd [Win-70]. As an application we show uniform optimality with respect to the number of multiplications and divisions needed for two algorithms: For deciding whether a number is a zero of several polynomials -- if this number and the coefficients of these polynomials are given as input data -- evaluation of each polynomial with Horner's rule and then testing the values for zero is optimal. For verifying that a vector satisfies a system of linear equations -- given the vector and the coefficients of the system as input data -- the natural algorithm is optimal. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-91-039.pdf |
Bibliographic Notes | ICSI Technical Report TR-91-039 |
Abbreviated Authors | P. Buergisser and T. Lickteig |
ICSI Publication Type | Technical Report |