Lower Bounds for Arithmetic Networks II: Sum of Betti Numbers

J.L. Montaña^{2,3}  J.E. Morais^{1,3}  Luis M. Pardo ^{1,3}

    This paper is published in
    Applicable Algebra in Engineering Communications and Computing
    Vol.  7, pages 41--51, 1996.

Abstract. We show lower bounds for the parallel complexity of membership problems in semialgebraic sets. Our lower bounds are obtained from the Euler characteristic and the sum of Betti numbers. We remark that these lower bounds are polynomial (an square root) in the sequential lower bounds obtained by Andrew C.C. Yao.

Keywords: Parallel complexity, Algebraic complexity theory, Arithmetic networks, Semialgebraic sets, Borel–Moore homology

0. Introduction.

Throughout these pages we deal with arithmetic decisional problems over real closed fields. They are stated as membership problems in languages W ⊆ ⨁_{n∈IN} IR = IR^{∗}, accepted by some theoretical device involving arithmetic operations, {+, −, ×, /}, and sign tests, {> 0, = 0, < 0}, as elementary operations. Our main goal is the analysis of the parallel time complexity of these problems, in terms of depth of arithmetic networks (cf. [9]). We extend the lower bounds obtained in [16] (based on connected components), using as new parameter the sum of Betti numbers.

Usually, the sequential model for this kind of problems is described by real RAMS (cf. [18], [23]) and real Turing machines (cf. [4], [7]). The non–uniform sequential model (required for an analysis of lower bounds) is given by sequences of algebraic computation trees {T_{n}}_{n∈IN} . To every node of the tree we assign an elementary operation and to every leaf we assign a YES/NO answer. The tree T_{n} describes the elementary operations performed on inputs x ∈ IR^{n}. The accepted set (points with affirmative answer) is given as W_{n} := W ∩ IR^{n}, which is a semialgebraic subset of IR^{n} ( cf. [4], [5], [7]).

Since the works of Dobkin and Lipton, [8], Steele and Yao, [20], and M. Ben–Or, [1], the analysis of lower bounds for sequential complexity has been oriented to relate the topology of the semialgebraic set W_{n} to the complexity of the problem (cf. also [17], [7]). The lower bounds obtained were of the kind Ω(log_{2}β_{0}(W_{n})) , where β_{0}(W_{n}) is the number of connected components of W_{n}, i.e. the 0− th Betti number.

1 Departamento de Matemáticas, Estadística y Computación. Facultad de Ciencias. Universidad de Cantabria.

E–39071 Santander, Spain

2 Departamento de Matemáticas e Informática. Universidad Pública de Navarra. Campus de Rosadía. Pamplona 31006. Navarra. Spain

3 Partially supported by 92–0498–C02–01, PB93–0472–C02–02 and “POSSO”, ESPRIT–BRA 6846.

One of the most challenging problems posed by these authors was to relate higher homology groups to the complexity of these problems. Let us denote by β_{r} the r− th Betti number, i.e. the rank of the r− th homology group. Thus, in [3] and [21], the authors stated that a modified Euler characteristic can be used for that purpose. Lately, in [2] the authors showed that the sum of Betti numbers can be used for the restricted model of linear trees. Finally, A.C.C. Yao has shown in [22] that if the W_{n} are compact sets, the sum of Betti numbers can be used to provide lower bounds for sequential complexity, i.e. they have sequential complexity in Ω(log_{2}(∑ β_{r}) − n) .

In these pages we deal with an analysis of the parallel complexity of the same kind of problems. The parallel model, corresponding to that sequential model, is that of parallel real RAM’s (pRAM) or parallel real Turing machines. The equivalent non–uniform model is given by sequences, N_{n}, of arithmetic networks over the reals (cf. [9] and [16]). This model improves the performance of the sequential one accepting simultaneous operations and sign tests.

Within this context, one of the main problems is to know which polynomial time sequential problems (problems in P_{IR} ) can be solved by polynomial size, polylogarithmic depth networks (problems in NC_{IR} ). Up to now, two are the main methods known to find problems in P_{IR} \NC_{IR} . The first one deals with semialgebraic sets involving a high degree irreducible polynomial. This technique is considered in a different context in [10]. For an analysis of the parallel time of elimination, they deal with polynomials as X^{2^{n}} − Y . In [6] the author uses high degree Fermat’s equation, X^{2^{n}} + Y^{2^{n}} − Z^{2^{n}}, to find polynomial problems that cannot be parallelized by networks.

The second method, developed in [16], uses topological lower bounds. There, we showed that the number of connected components provides lower bounds of order Ω (\sqrt{log_{2}(β_{0})/n}), where β_{0} is the number of connected components and n is the number of variables. This bound is shown to hold independently of the size of the network. Let us observe that the relation between sequential and parallel lower bounds obtained by connected components is polynomial (i.e. they differ just in one square root). Thus, it was conjectured that this feature holds whenever topological lower bounds are considered.

The main goal of the present pages is to state that this relation also holds for Euler characteristic and the sum of the Betti numbers, that is, we are able to prove that

Ω (\sqrt{\frac{log_{2}(∑ β_{r})}{n}})

is a lower bound for the parallel time.

As applications we obtain connected semialgebraic sets that describe problems that can not be parallelized by arithmetic networks (i.e. in P_{IR} \ NC_{IR} ).

1. Borel–Moore homology of Semialgebraic sets.

Semialgebraic sets are the usual subject of real algebraic geometry. The terminology we follow here is that of [5].

Definition 1.1. A subset W ⊆ IR^{n} is called a semialgebraic cell, if there are polynomials f_{1}, …, f_{s} ∈ IR[x_{1}, …, x_{n}] and sign conditions (ε_{1}, …, ε_{s}) ∈ {>, =}^{s} such that

W = \{\underline{x} ∈ IR^{n} | f_{1}(\underline{x})ε_{1}0, …, f_{s}(\underline{x})ε_{s}0\}.

A semialgebraic set is a finite union of semialgebraic cells. Clearly, finite unions, finite intersections and complements of semialgebraic sets are also semialgebraic. As usual, a semialgebraic set is said to be locally closed if it is given as the intersection of an open semialgebraic set with a closed one. For instance, semialgebraic cells are locally closed. A continous mapping is called semialgebraic when its graph is a semialgebraic set.

Compact semialgebraic subsets of IR^{n} are triangulable topological spaces (cf. [5], Chapter 9 and the references therein). Then, the homology of compact semialgebraic sets can be defined in terms of their triangulations.

For a semialgebraic set W , we denote by H_{r}(W) the r− th homology group of W and by β_{r}(W) its r− th Betti number. If V, W are two compact semialgebraic sets, V ⊆ W , H_{r}(W, V) denotes the r− th group of relative homology. We also denote by β(W) the sum of all Betti numbers of W (i.e. β(W) = ∑ β_{r}(W) ). Analogously, we denote by χ(W) (the Euler characteristic of W ) the alternate sum of all Betti numbers of W (i.e. χ(W) = ∑(−1)^{r}β_{r}(W) ).

In [15] , Milnor shows a relation between homology and descriptions of basic closed semialgebraic sets.

Theorem 1.2. (Milnor bound) Let f_{1}, …, f_{s} ∈ IR[x_{1}, …, x_{n}] be polynomials and D = ∑ deg(f_{i}) . For the semialgebraic subset W of IR^{n} given by W = \{\underline{x} ∈ IR^{n} : f_{1}(\underline{x}) ≥ 0, …, f_{s}(\underline{x}) ≥ 0\}, we have

β(W) ≤ (1 + D)^{n}.

Now, we briefly review the definition and properties of the Borel–Moore homology, which is our main tool in this paper.

Definition 1.3. (cf. [5]) Let W be a non–compact locally closed semialgebraic set. Then, there is a pair (Ẇ , η) , called the Alexandrov semialgebraic compactification of W , such that:

i) Ẇ is a compact semialgebraic set,

ii) η : W → Ẇ is a continuous semialgebraic function which is an homeomorphism over its image, iii) Ẇ \ η(W) consists of only one element.

The Alexandrov semialgebraic compactification (Ẇ , η) is invariant under semialgebraic homeomorphism. If W is closed, then its Alexandrov compactification is given by the inverse stereographic projection. The Borel–Moore homology of locally closed semialgebraic sets is defined as follows (c.f. [5], section 11.7).

Definition 1.4. Let W be a locally closed semialgebraic set. The Borel–Moore homology of W , H_{r}^{BM}(W) , is given by

H_{r}^{BM}(W) = H_{r}(W) if W is compact,
H_{r}^{BM}(W) = H_{r}(Ẇ , Ẇ \ η(W)) otherwise.

Here (Ẇ , η) is the Alexandrov semialgebraic compactification of W .

By coherence, let us denote by β_{r}^{BM}(W) the rank of the r− th Borel–Moore homology group and by β^{BM}(W) the sum of all these ranks. We also use the Borel–Moore Euler characteristic, which is given by χ^{BM}(W) = ∑_{i≥0}(−1)^{i}β_{i}^{BM}(W) .

The following is the key point of the use of Borel–Moore homology in our analysis.

Lemma 1.5. (c.f. [5], 11.7.15) Let W be a locally closed semialgebraic set and T a semialgebraic subset of W , closed in W . We have the following long exact sequence:

… ⟶ H_{r+1}^{BM}(W \ T) ⟶ H_{r}^{BM}(T) ⟶ H_{r}^{BM}(W) ⟶ H_{r}^{BM}(W \ T) ⟶ …

In particular, if W and T are two locally closed semialgebraic sets, T ⊆ W , T closed in W , we have

β_{r}^{BM}(W) ≤ β_{r}^{BM}(W \ T) + β_{r}^{BM}(T).

Under the same hypothesis, the Borel–Moore Euler characteristic is an additive function, i.e.

χ^{BM}(W) = χ^{BM}(W \ T) + χ^{BM}(T).

Next proposition links Borel–Moore homology and classical homology of the Alexandrov compactification, which will be of common use in the sequel.

Proposition 1.6. Let W be a non–compact locally closed semialgebraic set. Then,

β(Ẇ) = β^{BM}(W) + 1.

Proof: Let (Ẇ , η) be the Alexandrov semialgebraic compactification of W . First, for r = 0 , β_{0}(Ẇ) = β_{0}^{BM}(W) + 1 . This statement follows directly from [11], Corollary 13.11, observing that Ẇ \ η(W) is just a point. Now, since both Ẇ and Ẇ \ η(W) are compact sets, we have the long exact sequence

… ⟶ H_{r}(Ẇ \ η(W)) ⟶ H_{r}(Ẇ) ⟶ H_{r}^{BM}(W) ⟶ H_{r−1}(Ẇ \ η(W)) ⟶ ….

The exactness of this sequence gives:

i) For r > 1 : β_{r}(Ẇ) = β_{r}^{BM}(W) ii) β_{0}(Ẇ) − β_{1}(Ẇ) − 1 = β_{0}^{BM}(W) − β_{1}^{BM}(W).

In [21], A. Yao modified Euler characteristic to have an invariant which is also an additive function. This modified Euler characteristic can be stated as follows: By Hironaka’s triangulation theorem, every bounded semialgebraic subset of IR^{n} has a semialgebraic triangulation. This means that if W ⊆ IR^{n} is bounded and semialgebraic, there is D = {D_{α} : α ∈ A} an open simplicial decomposition of

E := ⋃_{α∈A} D_{α} ⊆ IR^{n}

and there is h : E → IR^{n} a semialgebraic homeomorphism onto h(E) , such that there is B ⊆ A such that

W = ⋃_{α∈B} h(D_{α}).

Thus, Yao defined the modified Euler characteristic of W as

χ̂(W) = ∑_{α∈B}(−1)^{dim(D_{α})}.

If the semialgebraic set W is not bounded χ̂(W) is defined to be χ̂(φ(W)) , where φ is the inverse stereographic projection from S^{n} \ {(0, …, 0, 1)} ( S^{n} being the sphere with radius 1 in IR^{n+1} ). This χ̂ is invariant under semialgebraic homeomorphism, it is an additive function and it coincides with the usual Euler characteristic when W is compact (cf. [21]).

Corollary 1.7. With the above notations, if W is a locally closed, we have χ̂(W) = χ^{BM}(W) .

Proof: If W is compact there is nothing to prove. Otherwise, let (Ẇ , η) be the Alexandrov semialgebraic compactification of W . First, observe that the Euler characteristic of Ẇ is χ^{BM}(W) + 1 . On the other hand, χ̂(W) = χ(Ẇ) − 1 . Thus,

χ̂(W) = −1 + ∑_{r≥0}(−1)^{r}β_{r}(Ẇ) = ∑_{r≥0}(−1)^{r}β_{r}(W).

Let F ⊆ IR[x_{1}, …, x_{n}] be a finite collection of polynomials. A semialgebraic set given as the intersection on sign conditions of polynomials in F is called an F− cell. A semialgebraic subset W of IR^{n} is called a complete F− cell if there are sign conditions ε_{f} ∈ {<, =, >} such that:

W = ⋂_{f∈F}{x ∈ IR^{n} : f(x)ε_{f}0}

i.e. if W can be given by a formula involving all polynomials in F. Now, the exact sequence of Lemma 1.5 extends to the following proposition.

Proposition 1.8. Let F = {f_{1}, …, f_{s}} ⊂ IR[x_{1}, …, x_{n}] . Let W be a locally closed semialgebraic set. Then, for every r:

i) β_{r}^{BM}(W) ≤ ∑ β_{r}^{BM}(F ∩ W) , where F runs over the set of complete F− cells. ii) χ^{BM}(W) = ∑ χ^{BM}(F ∩ W) , for the same set of F ’s.

Proof: Applying lemma 1.5 twice we have

β_{r}^{BM}(W) ≤ β_{r}^{BM}(\{\underline{x} ∈ W | f_{1}(\underline{x}) > 0\}) + β_{r}^{BM}(\{\underline{x} ∈ W | f_{1}(\underline{x}) = 0\})+
+β_{r}^{BM}(\{\underline{x} ∈ W | f_{1}(\underline{x}) < 0\})

χ^{BM}(W) = χ^{BM}(W ⋂\{\underline{x} ∈ IR^{n} | f_{1}(\underline{x}) > 0\}) + χ^{BM}(W ⋂\{\underline{x} ∈ IR^{n} | f_{1}(\underline{x}) = 0\})+

+χ^{BM}(W ⋂\{\underline{x} ∈ IR^{n} | f_{1}(\underline{x}) < 0\})

Continuing the process with every f_{i}, for i > 1 , we get the wanted result.

Next, we get an upper bound for the Borel–Moore homology of a locally closed semialgebraic subset W , given as a union of F− cells. We remark that the bound has the same order of magnitude than that of Milnor’s theorem (see Theorem 1.2 above), it depends exponentially on the number of variables and polynomially on the sum of the degrees. We start bounding homology of Alexandrov compactification.

Proposition 1.9. Let W be the semialgebraic subset of IR^{n}

W = \{\underline{x} ∈ IR^{n} : f_{1}(\underline{x}) ≥ 0, …, f_{r}(\underline{x}) ≥ 0\},

and D = ∑ deg(f_{i}) . Then,

| χ(Ẇ) |≤ β(Ẇ) ≤ (5 + D)^{n+1}

Proof: Let φ : IR^{n} ⟶ S^{n} \ {(0, …, 0, 1)} be the inverse stereographic projection given by

φ(x_{1}, …, x_{n}) = (\frac{2x_{1}}{∥\underline{x}∥^{2} + 1}, ⋯, \frac{2x_{n}}{∥\underline{x}∥^{2} + 1}, \frac{∥\underline{x}∥^{2} − 1}{∥\underline{x}∥^{2} + 1}) ,

where ∥\underline{x}∥ is the usual norm in IR^{n}. Observe that if (y_{1}, …, y_{n+1}) ∈ S^{n} \ \{(0, …, 0, 1)\} we have

(\frac{y_{1}}{1 − y_{n+1}} , ⋯, \frac{y_{n}}{1 − y_{n+1}} ) = φ^{−1}(y_{1}, …, y_{n+1})

Consequently,

Ẇ = φ(W) ∪ {(0, …, 0, 1} =

= \{\underline{y} ∈ IR^{n+1} : F_{1}(y_{1}, …, y_{n+1}) ≥ 0, …, F_{r}(y_{1}, …, y_{n+1}) ≥ 0, −(y_{1}^{2} + ⋯ + y_{n+1}^{2} − 1)^{2} ≥ 0\} ,

where

F_{i}(y_{1}, …, y_{n+1}) = (1 − y_{n+1})^{d_{i}}f_{i} (\frac{y_{1}}{1 − y_{n+1}} , ⋯, \frac{y_{n}}{1 − y_{n+1}} )

and d_{i} = deg(f_{i}) . As D + 4 is an upper bound for the sum of the degrees of polynomials F_{1}, …, F_{r+s}, −(y_{1}^{2} + ⋯ + y_{n+1}^{2} − 1)^{2} , applying theorem 1.3 we conclude that

β(Ẇ) ≤ (5 + D)^{n+1}.

This achieves the proof of the proposition.

Theorem 1.10. Let F ⊆ IR[x_{1}, …, x_{n}] be a finite family of polynomials and D the sum of the degrees of all polynomials in F. Then,

i) If W is a semialgebraic F− cell, β^{BM}(W) is at most 2(5 + 2D)^{n+1} ii) The same holds for | χ^{BM} |. iii) If W is a union of F− cells β^{BM}(W) is of order (1 + D)^{O(n)} . Proof: Let W be a F− cell,

W = \{\underline{x} ∈ IR^{n} : f_{1}(\underline{x}) = 0, …, f_{r}(\underline{x}) = 0, f_{r+1}(\underline{x}) > 0, …, f_{s}(\underline{x}) > 0\}.

Let us define the semialgebraic sets:

W′ = \{\underline{x} ∈ IR^{n} : −f_{1}^{2}(\underline{x}) ≥ 0, …, −f_{r}^{2}(\underline{x}) ≥ 0, f_{r+1}(\underline{x}) ≥ 0, …, f_{s}(\underline{x}) ≥ 0\} and

W′′ = \{\underline{x} ∈ IR^{n} : −f_{1}^{2}(\underline{x}) ≥ 0, …, −f_{r}^{2}(\underline{x}) ≥ 0, − ∏_{i=r+1}^{s} f_{i}^{2}(\underline{x}) ≥ 0, f_{1}(\underline{x}) ≥ 0, …, f_{s}(\underline{x}) ≥ 0\}.

Clearly, we have W′ = W ⋃ W′′, being W′ a closed semialgebraic set in IR^{n} and W′′ a closed semialgebraic set in W′. So, using lemma 1.7, we have that

… ⟶ H_{r}^{BM}(W′) ⟶ H_{r}^{BM}(W) ⟶ H_{r−1}^{BM}(W′′) ⟶ …

is part of an exact sequence. From the exactness, we conclude that for r ≥ 0 , the following holds :

β_{r}^{BM}(W) ≤ β_{r}^{BM}(W′) + β_{r−1}^{BM}(W′′)

where β_{−1}(W′′) is considered to be 0 . Consequently,

β^{BM}(W) ≤ β^{BM}(W′) + β^{BM}(W′′).

Now, from Propositions 1.6 and 1.9, we have:

β^{BM}(W) ≤ β^{BM}(W′) + β^{BM}(W′′) = β(Ẇ′) − 1 + β(Ẇ′′) − 1 ≤
≤ (5 + D)^{n+1} + (5 + 2D)^{n+1}.

As for iii) , since W is a union of F− cells, it is also a union of complete F− cells. Finally, since there are at most (1 + D)^{O(n)} non–empty F− cells (c.f. [12], [13], [16]), applying Proposition 1.8, the statement iii) follows.

2. Arithmetic networks.

2.1. Lower bounds. In this subsection, we show a general lower bound for the parallel time required to solve the membership problem for a semialgebraic subset of IR^{n}, in terms of its Borel– Moore homology. This lower bound extends the one given in [16] as a function of the number of connected components.

As in [16], our non–uniform model of computation is given by arithmetic networks. An arithmetic network N is an arithmetic circuit (or straight line program) augmented with a special kind of gates, called sign gates. A sign gate outputs 1 if their input is greater or equal than 0 and 0 otherwise. More precisely:

Definition 2.1. An arithmetic network N over IR is a directed acyclic graph where each node has indegree 0, 1 , or 2. Nodes with indegree 0 are either labeled as inputs or with elements of IR . Nodes with indegree 2 are labeled with the binary operators of IR , that is “+”, “-”, “ × ” and “/”. Nodes of indegree 1 are of a unique kind and are sign gates.

To each gate we inductively associate a function on the input variables in the usual way. In particular, the function associated to the output gate is the function computed by the arithmetic network. We say that a semialgebraic set W is accepted by an arithmetic network N if the function computed by N is just the characteristic function of W . In this case it is assumed that the output gate is a sign gate.

For an arithmetic network N , the size s(N) , is the number of gates in N . The depth d(N) of N , is the length of the longest path from some input gate to some output gate. We shall refer to d(N) as parallel time.

Remark 2.2.

i) There is an alternative definition of arithmetic network that combines arithmetic gates with Boolean gates using an interface between them (see [9]). This interface is given by two special gates, sign gates and selection gates. For a fixed sign condition ε ∈ {>, =, <}, the sign gate outputs the following Boolean values:

sign(f, ε) = \{ \begin{matrix}T, & if fε0 \\ F, & otherwise. \end{matrix}

The selection gates choose a particular input according to a Boolean instance. They have associated a function sel : IR × IR × {T, F} → IR defined by

sel(g, h, B) = \{ \begin{matrix}g, & if B=T \\ h, & otherwise. \end{matrix}

Observe that both models are equivalent. ii) Observe that the combination of arithmetic gates with sign gates may increase the number of

polynomials involved in the computation up to a number which is doubly exponential in the depth

2^{2^{d(N)}}.

An example of this feature can be founded in [16]. Thus, a direct application of bounds in Theorem 1.10 would yield to a lower bound of the kind Ω(log_{2}log_{2}β^{BM}(W)/n) . In spite of this feature, Theorem 2.3 shows that a parameter like the sum of Borel–Moore homology does not grow so fast. This will allow us to obtain better fitted lower bounds.

Theorem 2.3. Let W ⊂ IR^{n} be a locally closed semialgebraic set recognizable in parallel time h by an arithmetic network N , h = d(N) . Then, h is greater than

Ω (\sqrt{\frac{log_{2}β^{BM}(W)}{n}})

Proof: Let sgn(i, 1), …, sgn(i, r_{i}) be the sign gates of N whose depth is i ≤ h. For each pair (i, j) , 1 ≤ j ≤ r_{i}, let h_{i,j} be the function of (x_{1}, …, x_{n}) that the sign gate sgn(i, j) receives as input. Note that, h_{i,j} is a piecewise rational function of (x_{1}, …, x_{n}) . Since the indegree of the gates is bounded by 2, at level i the number r_{i} is bounded above by 2^{h−i} and the formal degree of h_{i,j} is bounded by 2^{i}. Thus, applying the upper bounds for the non–empty cells (cf. [12], [13], [14], or [16], lemma 1.2) we see that at level 1 there are at most:

(2^{h−1} × 2)^{O(n)}

satisfiable r_{1}− tuples of sign conditions for the family F_{1} = {h_{1,1}, …, h_{1,r_{1}}}. Now, applying proposition 1.8 we see that:

β^{BM}(W) ≤ ∑_{F_{i_{1}}^{1} complete F_{1}−cell} β^{BM}(W ∩ F_{i_{1}}^{1}) ≤ 2^{O(h.n)}β^{BM}(W ∩ F_{i_{1}}^{1}),

where F_{i_{1}}^{1} maximizes the set {β^{BM}(W ∩ F_{i_{1}}^{1})}_{i_{1}}. Each r_{1}− tuple of satisfiable sign conditions determines the output of the r_{1} sign gates at level 1 and thus, determines specific rational functions h_{2,2}, …, h_{2,r_{2}} in the variables (x_{1}, ⋯, x_{n}) as inputs for the sign gates at level 2. Since the number r_{2} of these gates is bounded by 2^{h−2} and the degree of their input functions is bounded by 2^{2} , applying again [12] we deduce that for each r_{1}− tuple σ of sign conditions there are at most:

(2^{h−2} × 2)^{O(n)}

satisfiable r_{2}− tuples of sign conditions for the family F_{2}^{σ} = {h_{1,1}^{σ}, …, h_{1,r_{1}}^{σ}} (the superscript σ is written to recall that these input functions depend on the preceding tuple of sign conditions). Now, applying proposition 1.8 we have that:

β^{BM}(W ∩ F_{i_{1}}^{1}) ≤ ∑_{F_{i_{2}}^{2} complete F_{2}(σ)−cell} β^{BM}(W ∩ F_{i_{2}}^{2}) ≤ 2^{O(h.n)} β^{BM}(W ∩ F_{i_{2}}^{2}),

for some σ (that σ corresponding to F_{i_{1}}^{1} ) and some F_{i_{2}}^{2} . Consequently,

β^{BM}(W) ≤ 2^{O(h.n)}2^{O(h.n)} β^{BM}(W ∩ F_{i_{1}}^{1} ∩ F_{i_{2}}^{2})

Iterating h times this argument we obtain a collection of rational families {F_{j}}_{1≤j≤h} and a collection (F_{i_{j}}^{j}) of complete F_{j}− cells (one for each j) such that, each F_{j} consists of specific rational functions {h_{j,1}, …, h_{j,r_{j}}} with degree bounded by 2^{j}. These specific rational functions {h_{j,1}, …, h_{j,r_{j}}} are determine by the r_{j−1}− tuple of sign conditions defining the set F_{i_{j−1}}^{j−1} . Finally, one gets the relation:

β^{BM}(W) ≤ \overbrace{2^{O(h.n)} ⋯ 2^{O(h.n)}}^{h} β^{BM}(W ∩ F_{i_{1}}^{1} ∩ … ∩ F_{i_{h}}^{h}).

Now, if W ≠ ∅, since F_{i_{h}}^{h} maximizes {β^{BM}(W ∩F_{i_{1}}^{1} ∩…∩F_{i_{h}}^{h})}_{i_{h}} we conclude that F_{i_{1}}^{1} ∩…∩F_{i_{h}}^{h} ⊂ W, and applying theorem 1.10 iii) we have:

β^{BM}(W) ≤ 2^{O(h^{2}.n)}2^{O(h.n)}.

Taking logarithms the proof is achieved.

Corollary 2.4. Let W ⊂ IR^{n} be a compact locally closed semialgebraic set recognizable in parallel time h by an arithmetic network N . Then, h is greater than

Ω (\sqrt{\frac{log_{2}(| χ(W) | +1)}{n}})

Corollary 2.5. Let W ⊂ IR^{n} be a compact topological surface recognizable in parallel time h by an arithmetic network N . Let g(W) be the genus of W . Then, h is greater than

Ω (\sqrt{\frac{log_{2}(g(W) + 1)}{n}})

Proof: Since W is a topological surface, we know, from the Classification Theorem, that W is homeomorphic either to a sphere or to a connected sum of g(W) torus or to a connected sum of g(W) projective planes. In the case of a sphere g(W) = 0 . In the case of a connected sum of torus we have g(W) = 2 − 2χ(W) . Finally, in the case of a connected sum of projective planes we have g(W) = 2 − χ(W) .

2.2. Applications. The task of separating the class of problems solved within polynomial resources and those solved in polynomial size but restricted to polylogarithmic depth, has been studied in several contexts. In the boolean context, it is well known the conjecture about the fact P ≠ NC. Here P means the class of polynomial problems and, NC is the class of problems solved by sequences of boolean circuits of polynomial size and polylogarithmic depth. In the boolean frame there is no proof about this conjecture.

After the work in [4] that introduces the structural approach in the environment of continuous computation, in particular, computation with real numbers, analogously to the boolean context, classes P_{IR} and NC_{IR} have been introduced in the real setting.

Following this direction, the class P_{IR} is defined in [4] restricting computational resources to a polynomial amount under the model of real Turing machines. This model can be shown as an uniformization of algebraic computation trees or arithmetic networks (see [7]).On the other hand, the class NC_{IR} is defined by means of sequences of arithmetic networks working within polynomial size and polylogarithmic depth. Uniformity conditions are giving using real Turing machines. Surprisingly, in the real setting the problem P_{IR} ≠ NC_{IR} has a positive answer.

The separation between these two complexity classes have been shown independently in [6], using high degree irreducible polynomials and, also in [16], using semialgebraic sets with a high number of connected components.

In this sense, theorem 2.1 and the above corollaries can be used to get examples of connected problems that can be solved in polynomial time, but cannot be solved within polylogarithmic depth.

As a first example, let B_{n} the semialgebraic set in IR^{3n} defined by

B_{n} = \overbrace{C_{n} × ⋯ × C_{n}}^{n},

where, C_{n} is the connected sum of 2^{n+1} torus together with its interior in IR^{3} :

C_{n} = ⋃_{j=0}^{2^{n}} {(x_{1}, x_{2}, x_{3}) ∈ IR^{3} : ((x_{1} − 5j)^{2} + x_{2}^{2} + x_{3}^{2} + 3)^{2} ≤ 16 ((x_{1} − 5j)^{2} + x_{2}^{2})}

We have that where C_{n} is the connected sum of 2^{n} + 1 torus together with its interior in IR^{3} . Then:

–The set B_{n} is a compact and connected semialgebraic set, and

–Its complement in IR^{n} is also connected.

This means that we cannot apply a technique only involving the number of connected components. Using the Borel–Moore homology we have that

β^{BM}(W) = β(W) ≥ 2^{n^{2}},

and so that the parallel time to solve the membership problem for B_{n} is bounded below by Ω(\sqrt{n}) . A divide and conquer argument tells us that the sequential time (in terms of real Turing machines) to solve this problem is polynomial in n. Then:

Corollary 2.7. The membership problem for B_{n} is in the class P_{IR} \ NC_{IR} .

Another example is given by the following algebraic set:

W_{n} = {(x_{1}, x_{2}, …, x_{2n}) ∈ IR^{2n} : (x_{2i−1} − 2j)^{2} + x_{2i}^{2} − 1 = 0, 0 ≤ j ≤ 2^{n}, 1 ≤ i ≤ n}

This is a compact and connected algebraic set. In fact, W_{n} it is equal to \overbrace{Z_{n} × ⋯ × Z_{n}}^{n}, where Z_{n} is the algebraic set in IR^{2} which is the connected sum of 2^{n} + 1 copies of S^{1} , i.e., Z_{n} = {(x_{1}, x_{2}) ∈ IR^{2} : (x_{1} − 2j)^{2} + x_{2}^{2} − 1 = 0, j = 0, …, 2^{n}}. Consequently, we have

β^{BM}(W) = β(W) ≥ 2^{n^{2}},

which, by theorem 2.1, gives that the parallel time to solve the membership problem for W is bounded below by Ω(\sqrt{n}) . Again, a divide and conquer argument allows to solve this problem in polynomial time.

Corollary 2.8. The membership problem for W_{n} is in the class P_{IR} \ NC_{IR} .

As a final example, let C_{N} be the algebraic subset of IR^{3} given by N coplanar and concurrent lines. The Alexandrov compatification of C_{N} is given as the union of N meridians of a sphere, passing trhrough two fixed poles (i.e. N concurrent spheric lines).

It is easy to obtain a procedure that recognizes C_{N} in sequential O(log_{2}N) arithmetic operations and sign tests. However, the homology of Ċ_{N} , and also the Borel–Moore homology of C_{N} , is of order O(N) . Our theorem 2.3 above shows that no procedure exists recognizing C_{N} in parallel time less than \sqrt{N}. The membership problem in C_{N} is another example where sequential and parallel time have same order of magnitude.

References.

[1] M. Ben–Or. “Lower bound for algebraic computation trees”, A.C.M. 15^{th} Symposium on Theory of Computation., (1983) 80–86

[2] A. Björner and L.Lovász. “ Linear decision trees, subspace arrangements and Möbis function”, Preprint (1992) .

[3] A.Björner, L.Lovász and A.Yao. “Linear decision trees: volume estimates and topological bounds.” In Proc. A.C.M. 24^{th} Symposium on Theory of Computing, (1992) 170–177

[4] L. Blum, M. Shub and S. Smale. “On a theory of computation and complexity over the real numbers: NP–completeness, recursive functions and universal machines”. Bulletin of the A. M. S., vol.21, n. 1 ,(1989) 1–46 [5] J .Bochnack, M. Coste, M-F. Roy. Géométrie algébrique réelle. Ergebnisse der Math., 3.Folge, Band

12, Springer–Verlag, Berlin, Heidelberg, New York, (1987).

[6] F. Cucker. “ P_{IR} ≠ NC_{IR} ”. To appear in J. of Complexity.

[7] F.Cucker, J.L. Montaña, L.M. Pardo.“Time Bounded Computations over the reals”. Int. J. of Alg. and Comp., Vol.2, No. 4 , (1992) 395–408.

[8] D.P. Dobkin, R.J. Lipton.“On the complexity of computations under varying sets of primitives”. J. of Comp. Syst. Sci. 18, (1979), 86–91.

[9] J.Von zur Gathen.“Parallel arithmetic computations:a survey”. In Mathematical Foundations on computer Science, 13^{th} Proc.,(1986) 93–112.

[10] N. Fitchas, A. Galligo, J. Morgenstern. “Algorithmes rapides en séquentiel et en parallele pour l’élimination de quantificateurs en géométrie élémentaire”. Seminaire de Structures Algebriques Ordennes, Université de Paris VII (1987).

[11] M.J.Greenberg, J.R.Harper. Algebraic Topology: A first course. Mathematics lecture note series 58. The Benjamin/Cummings Publishing Company, (1981)

[12] D.Grigorev. “Complexity of deciding Tarski algebra”. J. Symb. Comp., 5 (1988) 65–108

[13] J. Heintz.“Definability and fast quantifier elimination over algebraically closed fields”. Theor. Comp. Sci. 24, (1983) 239–278.

[14] J.Heintz, M.–F.Roy, P.Solernó. “Sur la Complexité du Principe de Tarski–Seidenbrg”. Bull. Soc. Math. France 118 (1990) 101–126

[15] J.Milnor. “On the Betti numbers of real varieties”. Proc. Amer. Math. Soc., 15 (1964) 275–280.

[16] J.L.Montaña and L.M.Pardo.“Lower bounds for Arithmetic Networks”. AAECC 4 (1993) 1–24.

[17] J.L. Montaña, Luis M. Pardo y T. Recio.“ The Non–Scalar Model of Complexity in Computational Semialgebraic Geometry”. In Proc. MEGA’90, Progress in Mathematics 94, Birkhäuser, (1991) 346–362.

[18] F.P. Preparata, M.I. Shamos “Computational Geometry, An Introduction”. Springer–Verlag Texts and Monographs in Computer Science, (1985).

[19] S. Smale. “On the topology of Algorithms,I”. Journal of Complexity 3 (1987) 81–89

[20] M.Steele and A.Yao.“Lower bounds for Algebraic Decision Trees”. J. Algorithms 3 (1982) 1–8.

[21] A. Yao.“Algebraic Decision trees and Euler characteristics”. Proceedings of 33^{rd} Annual IEEE on Foundations of Computer Science, (1992) 268–277.

[22] A. C.C. Yao. “Decision trees and Betti Numbers”. To appear in Proc. STOCS’94 (1994).

[23] F.F. Yao.“Computational Geometry”. In Handbook of Theoretical Computer Science. J. van Leeuwen, ed., Elsevier, Amsterdam (1990) 343–391.