TU Berlin

Fachgebiet Algorithmische AlgebraJournal Publications

Page Content

to Navigation

There is no English translation for this web page.

Journal Publications

Verification complexity of linear prime ideals
Citation key BL-Verification-Complexity-Of-Linear-Prime-Ideals
Author Peter Bürgisser and Thomas Lickteig
Pages 247-267
Year 1992
Journal J. Pure Appl. Alg.
Volume 81
Abstract The topic of this paper is the complexity of algebraic decision trees deciding membership in an algebraic subset $X$ in $R^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 linear type generalizing a result by Winograd (1970). 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.
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe