Bürgisser, Peter(D-BONN-I5); Lickteig, Thomas(D-BONN-I5)

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.