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