TU Berlin

Fachgebiet Algorithmische AlgebraPublications

Page Content

to Navigation

There is no English translation for this web page.

Search for Publication

Search for publications

All 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