On the computational structure of the connected components of a hard problem

The study of sparse sets has tremendous importance in Turing complexity the ory. Thus it is a natural task to work out a related notion for real number models of computation. This has not fully been done so far. In the present paper we suggest such a notion based on the computational structure of the connected components a set has. Even though our notion of well-structured sets is different in spirit from the classical sparseness property we will show that it shares some important features with the latter. We are going t o analyze the (non-)existence of well-structured complete sets within the B lum-Shub-Smale model of computation over the reals with linear operations a nd equality respectively inequality. Relations to exponential time classes are also drawn. (C) 1999 Published by Elsevier Science B.V. All rights rese rved.