|
 ABSTRACT
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[&dgr;1, …, &dgr;m] ⊂ Qm = Q(&dgr;1, …, &dgr;m), where &dgr;1, …, &dgr;m are algebraically independent elements over Q and the ordering in the field Qm is defined as follows. The element &dgr;1 is infinitesimal with respect to Q (i. e. 0 < &dgr;1 < &agr; for any rational number 0 < &agr; ∈ Q) and for each 1 ≤ i < m the element &dgr;i+1 > 0 is infinitesimal with respect to the field Qi (cf. [GV 88], [Gr 88]).
Thus, let an input quantifier-free formula &Xgr; for the first-order theory of real closed fields be given, containing atomic subformulae of the form ƒi ≥ 0, 1 ≤ i ≤ k where ƒi ∈ Zm[X1, …,Xn].
Any rational function g ∈ Qm(Y1, …, Y3) can be represented as g = g1/g2 where the polynomials g1, g2 ∈ Zm[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, &dgr;1, …,&dgr;m). In the sequel we assume that the following bounds are valid: degx1, …, xn(ƒi) < d, deg&dgr;1, …, &dgr;m (ƒi) < d0, l(ƒi) ≤ M, 1 ≤ i ≤ k (1)
where d, d0, M are some integers. Then the bit-length of the formula ⊟ 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)2(&Ogr;(n)) time.
We use the notation h1 ≤ P(h2, …, ht) for the functions h1 > 0, …, ht > 0 if for the suitable integers c, &ggr; the inequality h1 ≤ c(h2 ·…· ht)&ggr; 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[X1, …, Xn].
A semialgebraic set {&Xgr;} ⊂ (Qm)n is (uniquely) decomposable in a union of a finite number of connected components {⊟} = ⋓1≤i≤t {⊟i}, each of them in its turn being a semialgebraic set determined by appropriate quantifier-free formula ⊟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)&Ogr;(n) (see e. g. [GV 88], [Gr 88]).
We use the following way of representing the points u = (u1, …, un) ∈ (@@@@m)n (cf. [GV 88]). Firstly, for the field Qm (u1, …, un) a primitive element &eegr; is produced such that Qm (u1, …, un) = Qm[&eegr;], herewith a minimal polynomial @@@@(Z) ∈ Qm[Z] for &eegr; is indicated, furthermore &eegr; = &Sgr;1≤i≤n &agr;ivi for some integers 0 ≤ &agr;1, …, &agr;n ≤ degZ(@@@@). Also the expressions ui = &Sgr;0≤j<degz(@@@@) &bgr;(j)i &eegr;j are yielded, where &bgr;(j)i ∈ Qm. Secondly, for specifying the root &eegr; of the polynomial @@@@ a sequence of the signs of the derivatives of all orders @@@@′(&eegr;), @@@@(2)(&eegr;), …, @@@@(deg(@@@@)) (&eegr;) of the polynomial @@@@ in the point &eegr; is given. Thom's Lemma (see e. g. [FGM 88]) entails that the latter condition uniquely determines the root &eegr; of
@@@@.
We say that a point u satisfies (D, D0, M)-bound if the following inequalities hold: degZ(@@@@) < D; deg&dgr;1 , …, &dgr;m(@@@@), deg&dgr;1 , …, &dgr;m (&bgr;(j)i) ≤ D0; l (@@@@), l(&bgr;(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]).
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
Ca 88
|
|
| |
CG 83
|
Chistov, A. L. and Grigoriev, D. Yu., Subezponential-time Solving Systems of Algebraic Equations, volumes I and II (1983), Preprints LOMI E-9-83 and E-10- 83, Leningrad.
|
| |
Co 75
|
|
| |
FGM 88
|
Fitchas, N., Galligo, A. and Morgenstern, J., A lgorithmes Rapides en Sgquential et en Parallele pour l'Elimination de Quantificateurs en Gdomgtrie l~ldmentaire, UER de Math~matiques Univers~te de Paris VII (~988).
|
| |
Gr 86
|
Grigoriev, D. Yu., Computational Complexity in Polynomial Algebra, Proceedings of the International Congress of Mathematicians, Berkeley (1986), pp. 1452-1460.
|
| |
Gr 88
|
|
| |
GV 88
|
|
| |
Ta 51
|
Tarski, A., A Decision Method for Elementary Algebra and Geometry, University of California Press (1951).
|
| |
Vo 89
|
Vorobjov, N. N., Jr., Deciding Consistency of Systems of Polynomial in Ea;ponent Inequalities in $ubexponential Time, Notes of $ci. Seminars of Leningrad Department of Math. Steklov Institute 176 (1989), pp. 3- 52 (in Russian).
|
| |
VG 91
|
Vorobjov, N. N., jr. and Grigoriev, D. Yu., Counting Connected ComponenIs of a Semialgebraic Set in $ubezponcntial Time, Soviet Math. Dokl. (to appear).
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
I.1