how to test in subexponential time whether two points can be connected by a curve in a semialgebraic set  a subexponential-time algorithm is designed which finds the number of connected components of a semi-algebraic set given by a quantifier-free formula of the first-order theory of real closed fields (for a rather wide class of real close fields, cf. [gv 88], [gr 88]). moreover, the algorithm allows for any two points from the semi- algebraic set to test, whether they belong to the same connected component.  decidability of the mentioned problems follows from the quantifier elimination method in the first-order theory of real closed fields, described for the first time by a. tarski ([ta 51]). however, complexity bound of this method is nonelementary, in particular, one cannot estimate it by any finite iteration of the exponential function. g. collins ([co 75]) has proposed a construction of cylindrical algebraic decomposition, which allows to solve these problems in exponential time.  for an arbitrary ordered field f we denote by f f its uniquely defined real closure. in the sequel we consider input polynomials over the ordered ring zm z[δ1, …, δm] qm = q(δ1, …, δm), where δ1, …, δm are algebraically independent elements over q and the ordering in the field qm is defined as follows. the element δ1 is infinitesimal with respect to q (i. e. 0 < δ1 < α for any rational number 0 < α ∈ q) and for each 1 ≤ i < m the element δi+1 > 0 is infinitesimal with respect to the field qi (cf. [gv 88], [gr 88]).  thus, let an input quantifier-free formula for the first-order theory of real closed fields be given, containing atomic subformulae of the form i ≥ 0, 1 ≤ i ≤ k where i ∈ z& lt;subscrpt>m[x, …,xn].  any rational function g ∈ qm< ;/italic>(y1& lt;/subscrpt>, …, y3) can be represented as g = g 1/g where the polynomials g1, g2 ∈ z m[ y1, …, y3] are reciprocately prime. denote by l(g) the maximum of bit-lengths of the (integer) coefficients of the polynomials g1, g2 (in the variables y1, …, y3, δ1, …,δm). in the sequel we assume that the following bounds are valid: degx1, …, xn( i) < d, degδ1, …, δm ( i) < d0, l( i) ≤ m, 1 ≤ i ≤ k (1)  where d, d0, m are some integers. then the bit-length of the formula &amp;minusb; can be estimated by the value l = k m dn dm0 (cf. [cg 83], [gr 86]).  note that in the case m = 0, i. e. for the polynomials with integer coefficients, the algorithms from [co 75] allow to produce the connected components (in particular to solve the problems considered in the present paper) within polynomial in m (kd)( (n)) time.  we use the notation h1 ≤ & lt;italic>p(h2 ;, …, ht) for the functions h1 > 0, …, ht > 0 if for the suitable integers c, γ the inequality h1 ≤ c(h~~2 *…* t)γ ; is fulfilled.  recall that a semialgebraic set (in fn where f is a real closed field) is a set {ii} fn of all points satisfying a certain quantifier-free formula ii of the first-order theory of the field f with the atomic subformulae of the form (g ≥ 0) where the polynomials g ∈ f[< italic>x1, …, < ;italic>xn].  a semialgebraic set { } (qm&amp;l; t;/subscrpt>)n ; is (uniquely) decomposable in a union of a finite number of connected components {&amp;minusb;} = 1≤i≤t {&amp;minusb;i}, each of them in its turn being a semialgebraic set determined by appropriate quantifier-free formula &amp;minusb;i of the first-order theory of the field qm (see e. g. [co 75] for the field f = r, for an arbitrary real closed field one can involve tarski ([ta 51]). note that t ≤ (kd) (n) (see e. g. [gv 88], [gr 88]).  we use the following way of representing the points u = (u1, …, un< /italic>) ∈ (@@@@m )n ; (cf. [gv 88]). firstly, for the field qm (u1, …, un< /italic>) a primitive element is produced such that qm (u1, …, un< /italic>) = qm[ ], herewith a minimal polynomial @@@@(z) ∈ qm[z_] for is indicated, furthermore = 1≤i≤nαiv ;i for some integers 0 ≤ α1, …, αn ≤ degz(@@@@). also the expressions ui = 0≤jz(@@@@) β~~(j)&amp;l; t;italic>i j are yielded, where β(j)i ∈ qm. secondly, for specifying the root of the polynomial @@@@ a sequence of the signs of the derivatives of all orders @@@@′( ), @@@@(2)( ), …, @@@@(deg(@@@@)) ( ) of the polynomial @@@@ in the point is given. thom's lemma (see e. g. [fgm 88]) entails that the latter condition uniquely determines the root of @@@@.  we say that a point u satisfies (d, d0, m)-bound if the following inequalities hold: degz(@@@@) < d; degδ1 , …, δm(@@@@), degδ1 , …, δm (β(j)~~i) ≤ d0; l (@@@@), l(^ 6;(j)i) ≤ m  then the bit-length of the representation of the point u does not exceed p(m, d, dm0, n) (cf. [gv 88], [gr 88]). the main purpose of the paper is to prove the following theorem (see also [vg 91]).  d. y. grigoriev