94a:68048 68Q25 14P05
Bürgisser, Peter(D-BONN-I5); Lickteig, Thomas(D-BONN-I5)
Verification complexity of linear prime ideals.
(English. English summary)
J. Pure Appl. Algebra 81 (1992), no. 3, 247--267.
Lower bounds on the computational complexity of deciding membership in
certain types of algebraic sets defined over real or algebraically
closed fields are obtained. The results are formulated in terms of
algebraic geometry; by way of application, they are shown to imply
almost immediately that the natural methods of verifying that a number
is a zero of several polynomials, or that a vector satisfies a system
of linear equations, are optimal.
© Copyright American Mathematical Society 1994, 1997