On the computational structure of the connected components of a hard problem
The study of sparse sets has tremendous importance in Turing complexity theory. 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 to analyze the (non-)existence of well-structured complete sets within the Blum-Shub-Smale model of computation over the reals with linear operations and equality respectively inequality. Relations to exponential time classes are also drawn. (C) 1999 Published by Elsevier Science B.V. All rights reserved.
connected components sparseness computational complexity over the reals