English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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 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≤jz(@@@@) &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) ≤ MThen 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]).

How to test in subexponential time whether two points can be connected by a curve in a semialgebraic set