Lower bounds for arithmetic networks

    This paper is published in
    Applicable Algebra in Engineering, Communications and Computing
    vol.4, No.  1, Springer (1993) pages 1-24.

J. L. Montaña ^{†,‡}  L. M. Pardo ^{†,‡}

Dedicated to the Memory of Mario Raimondo

Abstract.- We show lower bounds for depth of arithmetic networks over algebraically closed fields, real closed fields and the field of the rationals. The parameters used are either the degree or the number of connected components. These lower bounds allow us to show the inefficiency of arithmetic networks to parallelize several natural problems. For instance, we show a \sqrt{n} lower bound for parallel time of the Knapsack problem over the reals and also that the computation of the “integer part” is not well parallelizable by arithmetic networks. Over the rationals we obtain results of similar order and that the Knapsack has an \sqrt{n} lower bound for the parallel time measured by networks. A simply exponential lower bound for the parallel time of quantifier elimination is also shown. Finally, separations among classes P_{K} and NC_{K} are available for fields K in the above cases.

Keywords : Parallel complexity, algebraic complexity theory, arithmetic networks, constructible and semialgebraic sets, degree and connected components .

0. Introduction.

Throughout these pages we deal with arithmetic decisional problems over fields K. They are stated as membership problems to languages L ⊆ ⨁_{n∈IN} K = K^{∗}, accepted by some theoretical device (represented by families of arithmetical networks, cf. [12]) involving arithmetic operations, {+, −, ×, /}, and polynomial sign conditions over K as intrinsic elementary operations. Our main goal is the analysis of the parallel complexity of these problems and we analyze parallel time in terms of depth of arithmetical networks. Our purpose is to find lower bounds for this depth.

Kung shows in [18] lower bounds for the evaluation of rational functions by arithmetic circuits. An analysis of lower bounds for evaluation of piecewise rational functions by arithmetic networks is done in [12]. In both cases the main technical tool is the geometric degree. The lower bound in [18] does not apply for networks. In [12] von zurGathen gives the lower bounds of type “log_{2}(thick − degree)” and “log_{2}(1 + log_{2}degree)”. However, the “thick-degree” is not useful when dealing with decisional problems, whereas “log_{2}(1 + log_{2}degree)” is far from being a precise lower bound for most natural problems.

† Departamento de Matemáticas, Estadística y Computación. Facultad de Ciencias. Universidad de Cantabria. 39071 - SANTANDER. Spain

‡ Partially supported by DGICyT PB 89/0379 and “POSSO”, ESPRIT-BRA 6846.

In section 2 we analyze lower bounds for acceptor networks over algebraically closed fields

obtaining one of the kind Ω (\sqrt{\frac{log_{2}degree}{n}}), (see theorem 2.3 below), where n is the dimension of

the space of inputs, namely K^{n}. This improves the results in [12] and produces an Ω(\sqrt{n}) lower bound for the following problem:

\underline{2^{n}-Root.-}
Given x ∈ K decide whether x^{2^{n}} − 1 = 0 or not.

Our lower bound will be also useful when dealing with an analysis of parallel complexity of quantifier elimination over algebraically closed fields (see section 4).

On the other hand, the degree is a geometric tool not very accurate when dealing with problems over ordered fields, as the field of real numbers IR, or the field of rational numbers, 0 Q. For instance, let us consider the Knapsack problem (K being an ordered field) :

Knapsack Problem .-

Given \underline{x} = (x_{1}, ⋯, x_{n}) ∈ K^{n}, decide whether \underline{x} belongs to the following semialgebraic set:

K_{n} = \{\underline{x} ∈ K^{n} : ∃S ⊆ \{1, ⋯, n\}, ∑_{i∈S} x_{i} = 1\}

No known method based on the degree produces meaningful lower bounds for the parallel time of this problem. If K is a real closed field we replace degree by number of (semialgebraically) connected

components, β_{0}, and in section 3 we obtain a lower bound for depth of the kind Ω (\sqrt{\frac{log_{2}β_{0}}{n}} ), (see

theorem 3.1 below). This leads to an Ω(\sqrt{n}) lower bound for the parallel time of the Knapsack problem over any real closed field.

Connected components do not apply immediately for the field of rationals. In section 3, theorem 3.5, we state lower bounds of the same order than those stated for real closed and algebraically closed fields. In particular, these lower bounds apply to show an \sqrt{n} lower bound for the parallel time of Knapsack Problem over 0 Q and that the computation of the “integer part” of a rational number can not be efficiently parallelized by networks.

In section 4, using our lower bounds, we compare the efficiency of arithmetic networks when parallelizing different models of sequential arithmetic procedures: algebraic computation trees (cf.

[2] or [22]), linear search programs (cf. [20]) or Turing machines over a field K (cf. [4]). In fact, in section 4 we show that all these sequential models can not be efficiently parallelized − in polylogarithmic depth − by networks.

Finally, our lower bounds technique simplifies the proof of an exponential lower bound for the parallel time of quantifier elimination over algebraically closed and real closed fields as shown in [9] and [11].

1. Ground tools and definitions: the presence of selection gates.

Let K be an arbitrary field, ordered or not, a subset W ⊆ K^{n} is said to be constructible over K if there is a finite number of polynomials f_{i,j} ∈ K[X_{1}, ⋯, X_{n}], i=1,...,r, j=1,...,s and sign conditions ε_{i,j} such that:

W = ⋃_{j=1}^{s}\{\underline{x} ∈ K^{n} : f_{1,j}(\underline{x}) ε_{1,j} 0, ⋯, f_{r,j}(\underline{x}) ε_{r,j} 0\}

where the sign conditions are of the form:

ε_{i,j} ∈ {=, ≠}, if K is arbitrary (e.g. algebraically closed). ε_{i,j} ∈ {>, =, <}, if K is ordered (e.g. real closed or K = 0 Q).

When K is real closed, constructible subsets of K^{n} are usually called semialgebraic sets (see [3] or [5]). A constructible set given only by intersections of polynomial sign conditions (i.e. s = 1 above) is usually called a cell. If the field K is real closed cells are called semialgebraic cells. The degree of an irreducible algebraic set is the maximum of the cardinals of finite intersections with linear affine varieties. For general algebraic sets the degree is the sum of the degrees of its irreducible components. Finally, for a constructible set W ⊆ K^{n}, its degree deg(W) is the degree of its Zariski closure (see [16] for a more detailed description ^{1}). For real closed fields and semialgebraic subsets, W ⊆ K^{n}, we shall denote by β_{0}(W) the number of semialgebraically connected components (cf. [5]).

An arithmetic network N over a field K is an arithmetic circuit augmented with a boolean component and an interface between them. The boolean component is a boolean circuit, the interface is given by two special gates, sign gates −arithmetic input and boolean output− and selection gates −two boolean arithmetic inputs and one boolean input, one arithmetic output− that select an arithmetic value according with a boolean one.

The definitions of size and depth for arithmetic networks are the natural extensions of the corresponding concepts for boolean circuits and arithmetic circuits. We shall denote by D(N) the depth of the arithmetic network N .

When dealing with arithmetic networks we must make some precisions according to the nature −ordered or not− of the ground field K. In [12] only the non ordered case is treated, but we are also interested in the ordered one.

If the field K is not necessarily ordered, we suppose that the sign gates are of the following form:

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

In the case of an ordered field, (K, ≤), sign gates require a bit more of attention. A sign gate in this case is of the form sgn(−, ε), with ε ∈ {<, =, >}. They are defined by

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

Selection gates (see Fig.1 below) have associated a function sel : K ×K ×{T, F} → K defined by

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

1 In the CORRIGENDUM of [16], J. Heintz remarked that Bezout’s Inequality for constructible sets does not hold for this wide concept of degree. This author also observes that it still holds for locally closed constructible sets and Theorem 1.1 below remains true. In the sequel we only need this theorem 1.1 and that this concept of degree is a subadditive function.

When no boolean element −selection, sign or boolean gates− occurs, an arithmetic network is simply an arithmetic circuit (or straight line program as e.g. in [27]). Thus, it computes a rational mapping ϕ : K^{n} ⟶ K^{m}, where m is the number of output nodes. In [18] Kung showed the following:

Theorem A.- ([18]) Let N be an arithmetic circuit that computes a rational mapping ϕ : K^{n} ⟶ K^{m}. Then

D(N) = Ω(log_{2}deg(ϕ))

f

g  h  sign( f , ε )

Selection( g , h , B )

Fig.1.- The structure of Selection gates related to sign gates.

Let now be given an arithmetic network N with inputs in K^{n}, m arithmetic output nodes and ν boolean output nodes. It evaluates a function:

ϕ = (ϕ^{A}, ϕ^{B}) : K^{n} ⟶ K^{m} × {F, T}^{ν}

Selection gates make ϕ^{A} = (f_{1}, ⋯, f_{m}) to be a piecewise rational mapping, i.e. the entry f_{j} associated to the j − th arithmetic output node is given by

f_{j} = ∑_{i=1}^{t} h_{i,j}.χ_{W_{i,j}}

where h_{i,j} is a rational function and χ_{W_{i,j}} : K^{n} ⟶ {0, 1} is the characteristic function of a constructible set W_{i,j} ⊆ K^{n}: χ_{W_{i,j}}(\underline{x}) = 1 iff \underline{x} ∈ W_{i,j}. The entries of the mapping ϕ^{B} = (φ_{1}, ⋯, φ_{ν}), φ_{i} : K^{n} ⟶ {T, F}, are the membership problem function for a constructible set.

In [12] J. von zurGathen showed that the logarithm of the degree of the piecewise rational function is not a lower bound for depth of arithmetic networks evaluating the mapping. In that paper, the degree of ϕ^{A} is defined in the following terms:

− deg(ϕ^{A}) = max{deg(Gr(f_{j})) : j = 1, ⋯, m}. where Gr(f_{j}) is the constructible set in K^{n+1} given as the graph of the piecewise rational function f_{j}.

Then, the author introduced in [12] the conept of “thick-degree” as: “the maximum of the degrees in the Zariski dense pieces of the partition”, i. e. :

− thick − degree(f_{j}) = max{deg(Gr(h_{i,j})) : W_{i,j} is Zariski dense in K^{n}}.

− thick − degree(ϕ^{A}) = max{thick − degree(f_{j}) : j = 1, ⋯, m}.

Observe that if W_{i,j} is Zariski dense in K^{n}, deg(Gr(h_{i,j})) is just the degree of the rational function h_{i,j}.

With these conventions, we have :

Theorem B.- [12] Let K be an infinite field and N an arithmetic network computing ϕ. Then

D(N) ≥ log_{2}(thick − degree(ϕ)).

For algebraically closed fields, the following general result holds.

Theorem C .- [12] Let K be an algebraically closed field and N an arithmetic network that computes the function ϕ. Then

D(N) ≥ log_{2}(1 + log_{2}deg(ϕ)).

In this paper we shall be mainly concerned with decision problems (m = 0 and ν = 1 above). Thus, we deal only with arithmetic networks having just one output node which is either a boolean gate or a sign gate. We call them acceptor networks. Thus, an acceptor network N simply test the sign of a piecewise rational function, which means it decides the membership problem for a constructible subset W(N) of K^{n}.

The thick-degree is not very accurate when dealing with lower bounds for decision problems. Let us note that an arithmetic network N that solves the membership problem to a constructible set W(N) ⊆ K^{n}, also evaluates the piecewise rational function χ_{W(N)} : K^{n} ⟶ K and conversely. However, the thick-degree of χ_{W(N)} is always zero. This implies that theorem B does not produce lower bounds for decisional problems.

On the other hand, theorem A does not apply for decisional problems, and theorem C does not produce meaningful lower bounds for natural problems. For instance, theorem C provides an Ω(log_{2}n) lower bound for the 2^{n}−Root problem of the Introduction.

Finally, many natural problems are stated over ordered fields as 0 Q and IR. The Knapsack Problem is one of them. Knapsack Problem over 0 Q is a well-known NP-complete problem, while Knapsack over IR has been studied in depth: an Ω(n^{2}) lower bound for sequential time has been shown in [2] and a non-uniform polynomial upper bound − under the model of linear search programs − can be found in [20].

Our main purpose in these pages is to fill in the gap produced by this lack of lower bounds for parallel time. For instance, we can show an Ω(\sqrt{n}) lower bound for depth of acceptor networks solving the 2^{n}−Root problem (Cor. 4.6.1) and also an Ω(\sqrt{n}) lower bound for parallel time of the Knapsack Problem both over 0 Q (Cor. 4.4.1) and IR (Cor. 4.2.1).

We shall follow a strategy based on two central points:

Assume that K is a field and F ⊆ K[X_{1}, . · · · , X_{n}] a finite family of polynomials, D = ∑_{f∈F} deg(f). As in [16], an F-cell is a cell given as intersection of {=, ≠} −sign conditions on the polynomials of F. Recall the following

Theorem 1.1. (cf. [16]) Let K be an algebraically closed field. With the notations above we have:

i) for every F-cell, W, deg(W) ≤ (1 + D)^{n}.

ii) the total number of non-empty F-cells is bounded by (1 + D)^{n}.

On the other hand, assume (K, ≤) an ordered field, F and D as above. A semialgebraic F-cell is a cell given as intersection of {>, =, <}−sign conditions on the polynomials of F. We have the following:

Lemma 1.2. ([14], [17]) Assume that K is a real closed field, the number of non-empty F-cells is of order D^{O(n)}. Furthermore, the number of connected components of any semialgebraic set of the form W = ∪_{j}W_{j} where W_{j} is a semialgebraic F-cell is of order D^{O(n)}. Proof: First consider C = K[i], i^{2} = −1, the algebraic closure of K. The number of non-empty F-cells in C^{n} of the form

f_{1}(\underline{x}) = 0, ⋯, f_{t}(\underline{x}) = 0,
f_{t+1}(\underline{x}) ≠ 0, ⋯, f_{l}(\underline{x}) ≠ 0,

is bounded by (1 + D)^{n}. The total number of connected components of semialgebraic F-cells of the kind

f_{1}(\underline{x}) = 0, ⋯, f_{t}(\underline{x}) = 0,
f_{t+1}(\underline{x}) > 0, ⋯, f_{l}(\underline{x}) > 0,
f_{l+1}(\underline{x}) < 0, ⋯, f_{k}(\underline{x}) < 0,

is bounded by the number of connected components in K^{n} of the semialgebraic set defined by

f_{1}(\underline{x}) = 0, ⋯, f_{t}(\underline{x}) = 0, ∏_{j=t+1}^{k} f_{j}(\underline{x}) ≠ 0.

By [21] the number of connected components of the previous semialgebraic set is of order D^{O(n)}. Hence the total number of non-empty semialgebraic F-cells does not exceed D^{O(n)}. The second part of the statement follows from the first one.

We analyze the role of selection gates in arithmetic networks in the following pages:

Lemma 1.3. Let N be an acceptor network without selection gates over a field K: i) If K is algebraically closed we have:

D(N) = Ω (\frac{log_{2}deg(W(N))}{n})

ii) If K is a real closed field we have:

D(N) = Ω (\frac{log_{2}β_{0}(W(N))}{n})

Proof: Denote d = D(N). Since N is an acceptor network it has just an output node. Thus, the size of N is bounded by 2^{d+1}. Since there is no selection gate we observe the following facts:

− All the ancestors of an arithmetic gate or a sign gate are also arithmetic gates.

− The output of a sign gate is either the input to a boolean gate or this sign gate is the output gate.

On the other hand, the total number of sign gates S is bounded by the size of the network: S ≤ 2^{d+1}. Enumerate the sign gates and we have the following respective situations:

− For K algebraically closed, the sign gates have the form: sign(f_{i}) where f_{i} is the output of an arithmetic gate, i = 1, ⋯, S. − For K real closed, the sign gates have the form : sign(f_{i}, ε_{i}), where f_{i} is the output of an arithmetic gate, ε_{i} ∈ {>, =, <}, for i = 1, ⋯, S.

Consider the family F = {f_{1}, ⋯, f_{S}}. Since all the ancestors of a sign gate are arithmetic gates, f_{i} is computed by an arithmetic circuit of depth smaller than d. This implies by theorem A that deg(f_{i}) ≤ 2^{d}. Moreover, a sign gate is only followed by boolean gates. Thus the set accepted by the network W(N) is a finite union:

W(N) = ∪_{i∈I}W_{i}

where, W_{i} is an F-cell if K is algebraically closed and W_{i} is a semialgebraic F-cell if K is real closed. Now observing that ∑_{i=1}^{S} deg(f_{i}) ≤ 2^{O(d)}, we conclude from theorem 1.1 and lemma 1.2

deg(W(N)) = 2^{O(d.n)}
β_{0}(W(N)) = 2^{O(d.n)}

The lemma follows now taking logarithms.

This general strategy works whenever the number of polynomials involved in the description of W(N) is in 2^{O(D(N))}. However the presence of selection gates increases very fast this number. The network N of Fig. 2, with inputs in IR^{2} and depth log_{2}n, involves 2^{O(n)} polynomials, i.e. the number of polynomials involved in the description of the accepted set is doubly exponential in the depth of the network.

Consider, for instance, {a_{i} : i = 1, ⋯, 3n} ⊆ IR, a_{i} > 0 a collection of 3n positive real numbers and f_{i} = X^{2} + Y^{2} − a_{i} in Fig. 2 below. Observe that every selection gate k ∈ {0, ⋯, n − 1} outputs two posible different polynomials : X^{2} + Y^{2} − a_{3k+1} and X^{2} + Y^{2} − a_{3k+2}. When operating the outputs of two selection gates we are involving four polynomials at the first stage : (X^{2} + Y^{2} − a_{1}).(X^{2} + Y^{2} − a_{4}), (X^{2} + Y^{2} − a_{1}).(X^{2} + Y^{2} − a_{5}), (X^{2} + Y^{2} − a_{2}).(X^{2} + Y^{2} − a_{4}) and (X^{2} + Y^{2} − a_{2}).(X^{2} + Y^{2} − a_{5}). Inductively, this amounts up to 2^{n} polynomials involved in the description of the accepted set:

W(N) = {f_{3} = 0, f_{6} = 0, ⋯, f_{3n} = 0, f_{1}.f_{4}. · · · .f_{3n−2} ≠ 0} ⋃ ⋯
⋯ ⋃{f_{3} ≠ 0, f_{6} ≠ 0, ⋯, f_{3.n} ≠ 0, f_{2}.f_{5}. · · · .f_{3n−1} ≠ 0}

In fact, the description above means that we are involving all possible products

∏_{k=0}^{n−1} f_{s(k)}

where s(k) is either 3k + 1 or 3k + 2.

f_{3}  ⋯  f_{3.k+3}  ...  f_{3.n}
↓  ⋯  ↓  ...  ↓
f_{1}  f_{2} sign(f_{3}, =) ⋯ f_{3.k+1} f_{3.k+2} sign(f_{3.k+3}, =)...f_{3.n−2} f_{3.n−1} sign(f_{3.n}, =)
↘  ↓  ↙  ⋯  ↘  ↓  ↙  ... ↘  ↓  ↙
sel_{0}(., ., .)  sel_{1}(., ., .) ⋯ sel_{k}(., ., .) ⋯ sel_{n−2}(., ., .) sel_{n−1}(., ., .)
↘  ↙  ↘  ↘  ↙
⨀ ×  ⋯  ⨀ ×  ⋯ ⨀ ×  ⨀ ×  ⋯ ⨀ ×
↘  ⋯ ↙  ⋯ ↘  ↙  ⋯ ↙
⨀ ×  ⋯  ⨀ ×  ⋯ ⨀ ×
↘  ⋯  ↘  ⋯ ↙
· · · · · · · · · · · · · · ·· · · · · · · · ·· · · · · · · · ·
⨀ ×  ⨀ ×
↘  ↙
⨀ ×
↓
sign(., ≠)

Fig. 2.- An arithmetic network involving a doubly exponential number of polynomials

If we would apply directly theorem 1.1 and lemma 1.2 we obtain an upper bound for the number of connected components which is doubly exponential in the depth of the network, namely β_{0}(W(N)) ≤ 2^{2^{D(N)+1}} = 2^{O(n)}. This immediate argument would lead to a lower bound similar to that of theorem C. However, a finer argument provides a better relation between depth and number of connected components. Let us observe that the accepted semialgebraic set W(N) is given as a finite union W(N) = ⋃ L_{i,1} ∩ L_{i,2}, where:

− L_{i,1} is an F-cell, being F = {f_{3}, f_{6}, ⋯, f_{3n}}.

− L_{i,2} is given as {∏_{k=0}^{n−1} f_{s(k)} ≠ 0}, where the selection of the polynomial f_{s(k)} depends

on the sign of f_{3k+3}.

Now from lemma 1.2 the number of non-empty F-cells is of order (1 + D)^{2} = O(n^{2}), where D = ∑ deg(f_{3k+3}). Moreover, from lemma 1.2 the number of connected components of any intersection L_{i,1} ∩ L_{i,2} is of order O(n^{2}). Finally the total number of connected components is bounded by the following sum, where the index i runs over the family of those L_{i,1} ≠ ∅,

β_{0}(W(N)) ≤ ∑ β_{0}(L_{i,1} ∩ L_{i,2})

This implies a bound O(n^{4}), which is of order 2^{O(D(N))}.

This is the general strategy that, inductively on the depth of selection and sign gates, we shall follow to find better lower bounds in the following sections.

2. Lower Bounds for Depth over Algebraically closed Fields

In the previous section we have seen how selection gates increase very strongly the family of polynomials occuring in the description of the accepted set W(N). In spite of this feature we shall see here that a parameter like the degree does not grow so fast. This will allow us to obtain better fitted lower bounds.

Remark 2.1. Observe that boolean gates {∨, ∧, ¬} in arithmetic networks with inputs in K^{n} can be replaced by combinations of sign, selection and arithmetic gates in constant depth and size.

Remark 2.2. Let N be an arithmetic network with inputs in K^{n}. Let F be the family of all piecewise rational functions associated to any sign gate of N. Assume W ⊆ K^{n} a constructible subset verifying:

“For every f ∈ F the sign of f |_{W} is constant”

Now let us consider an output gate node ρ of N associated to a piecewise rational function f_{ρ} : K^{n} ⟶ K. We claim that there is a rational function h_{ρ} : K^{n} ⟶ K such that h_{ρ} can be computed by an arithmetic circuit of depth ≤ D(N) and that verifies f_{ρ} |_{W} = h_{ρ} |_{W}. In particular, the rational function h_{ρ} has degree bounded by 2^{D(N)}.

In order to prove this claim consider N′ the subnetwork of N formed by all the ancestors of the ouput node ρ. This network evaluates the piecewise rational function f_{ρ}. However the role played by sign gates and selection gates in N′ is superfluous when we consider inputs from W: they always have the same output for inputs from W. Thus, since we are restricting ourselves to inputs from W, we can remove all these unnecessary sign and selection gates. Finally, we obtain an arithmetic circuit C of depth at most D(N′) ≤ D(N) that computes a rational function h_{ρ} verifying the required conditions.

Now we are able to show the following lower bound.

Theorem 2.3. Let K be an algebraically closed field and N an acceptor network with inputs from K^{n}. Then, N verifies

D(N) = Ω (\sqrt{\frac{log_{2}deg(W(N))}{n}})

Proof: Let us introduce some notations concerning the sign gates of the network. Let (V, R), R ⊆ V × V, be the directed graph of N and G ⊆ V the set of all sign gates in N. For every path Γ := ρ_{1} → ρ_{2} → ⋯ → ρ_{k} in (V, R), we define the sign height of Γ as the number of sign gates in Γ, i.e. the cardinal of G ∩ {ρ_{1}, ⋯, ρ_{k}}.

For a sign gate ρ ∈ G we define the sign depth of ρ as the maximum of the sign heights of any path Γ in (V, R) ending at ρ. Let us denote by G_{i} the set of all sign gates in N of sign depth i. From remark 2.1 we can assume that N contains no boolean gate. Since N is an acceptor network, the unique output gate is a sign gate of sign depth t. Moreover, t is the maximum sign depth of any sign gate in N and t ≤ D(N).

For i = 1, ⋯, t we enumerate the elements of G_{i} from 1 to ♯(G_{i}), and we encode the sign gates of N as pairs (i, j) where i is the sign depth of the gate and j is the corresponding value of the enumeration. In particular, the output gate is encoded as (t, 1).

Let us also observe that since N is an acceptor network, the size of N is bounded by 2^{D(N)+1} and the cardinals of G and G_{i} are at most 2^{D(N)+1}.

Associated to a sign gate (i, j) there is a piecewise rational function f_{i,j} : K^{n} ⟶ K, which is evaluated by the subnetwork of N formed by all the ancestors of the gate (i, j). For \underline{ε} = (ε_{i,j}) ∈ \{=, ≠\}^{G}, let us denote by L\underline{ε} the constructible set

L\underline{ε} := ⋂_{(i,j)∈G}\{\underline{x} ∈ K^{n} : f_{i,j}(\underline{x})ε_{i,j}0\}

For a collection of sign conditions \underline{ε} = (ε_{i,j}) as above and i ∈ \{1, ⋯, t\}, denote by \underline{ε}_{i} ∈ \{=, ≠\}^{G_{i}} the element described by \underline{ε}_{i} := (ε_{i,j})_{(i,j)∈G_{i}}. Define:

L_{\underline{ε}_{i}} := ⋂_{(i,j)∈G_{i}}\{\underline{x} ∈ K^{n} : f_{i,j}(\underline{x})ε_{i,j}0\}

and observe that L\underline{ε} = ∩_{i=1}^{t}L_{\underline{ε}_{i}}

Lemma 2.4 For every \underline{ε} = (ε_{i,j}) ∈ \{=, ≠\}^{G}, there are rational functions h_{i,j} of degree ≤ 2^{D(N)} such that

L\underline{ε} = ⋂_{i=1}^{t} L_{\underline{ε}_{i}} := ⋂_{(i,j)∈G}\{\underline{x} ∈ K^{n} : h_{i,j}(\underline{x})ε_{i,j}0\}

Proof: We shall proceed by finite induction on the number of intersected L_{\underline{ε}_{i}}’s: k ≤ t.

For k = 1, the ancestors of any sign gate (1, j) are arithmetic gates. Then, f_{1,j} is a rational function, it is computed by an arithmetic circuit of depth ≤ D(N) and the assertion follows. Thus, assume that ∩_{i=1}^{k−1}L_{\underline{ε}_{i}} verifies the wanted conditions. Now the role played by selection gates which are ancestors of (k, j) on inputs in ∩_{i=1}^{k−1}L_{\underline{ε}_{i}} is superfluous. As in remark 2.2, there is an arithmetic circuit of depth ≤ D(N) that computes a rational function h_{k,j} : K^{n} ⟶ K such that:

h_{k,j} |_{∩_{i=1}^{k−1}L_{\underline{ε}_{i}}} = f_{k,j} |_{∩_{i=1}^{k−1}L_{\underline{ε}_{i}}}

Then,

⋂_{i=1}^{k} L_{\underline{ε}_{i}} = ⋂_{i=1}^{k−1} L_{\underline{ε}_{i}} ⋂\{\underline{x} ∈ K^{n} : h_{k,j}(\underline{x})ε_{k,j}0, for (k, j) ∈ G_{k}\}

And the statement follows.

Lemma 2.5. With these notations we have

♯\{\underline{ε} ∈ \{=, ≠\}^{G} : L\underline{ε} ≠ ∅\} = 2^{O(D(N)^{2}.n)}

Proof: Define the sets of sign conditions:

B_{1} := \{\underline{ε} = (ε_{1,j}) ∈ \{=, ≠\}^{G_{1}} : L\underline{ε} ≠ ∅\}

B_{2}(\underline{ε}_{1}) := \{\underline{ε} = (ε_{2,j}) ∈ \{=, ≠\}^{G_{2}} : \{\underline{x} : L_{\underline{ε}_{1}} ⋂ L\underline{ε} ≠ ∅\}, for \underline{ε}_{1} ∈ B_{1}

· · · · · · · · · · · · · · · · · ·

B_{t}(\underline{ε}_{1}, ⋯, \underline{ε}_{t−1}) := \{\underline{ε} = (ε_{t,1}) ∈ \{=, ≠\} : L_{\underline{ε}_{1}} ⋂ ⋯ ⋂ L_{\underline{ε}_{t−1}} ⋂ L\underline{ε} ≠ ∅\}

where \underline{ε}_{1} ∈ B_{1}, ⋯, \underline{ε}_{t−1} ∈ B_{t−1}(\underline{ε}_{1}, ⋯, \underline{ε}_{t−2}). Now observe that for \underline{ε}_{k} ∈ B_{k}(\underline{ε}_{1}, ⋯, \underline{ε}_{k−1}):

L_{\underline{ε}_{1}} ⋂ ⋯ ⋂ L_{\underline{ε}_{k}} = L_{\underline{ε}_{1}} ⋂ ⋯ ⋂ L_{\underline{ε}_{k−1}} ⋂\{\underline{x} : h_{k,j}(\underline{x}) ε_{k,j} 0, for j ∈ G_{k}\}

where h_{k,j} are the rational functions of degree 2^{D(N)} obtained in lemma 2.4. Defining F_{k} = {h_{k,j} : j ∈ G_{k}} we observe

♯ (B_{k}(\underline{ε}_{1}, ⋯, \underline{ε}_{k−1})) ≤ the number of non-empty F_{k}-cells

This implies, by theorem 1.1, that

♯ (B_{k}(\underline{ε}_{1}, ⋯, \underline{ε}_{k−1})) ≤ 2^{O(D(N).n)}

Thus, for \underline{ε} such that L\underline{ε} ≠ ∅, we have :

\underline{ε}_{1} ∈ B_{1}
\underline{ε}_{2} ∈ B_{2}(\underline{ε}_{1})
· · · · · · · · · · · ·
\underline{ε}_{t} ∈ B_{t}(\underline{ε}_{1}, ⋯, \underline{ε}_{t−1})

Inductively we can prove:

♯ \{\underline{ε} ∈ \{=, ≠\}^{G} : L\underline{ε} ≠ ∅\} ≤ ♯(B_{1}) × max\{♯B_{1}(\underline{ε}_{1})\} × ⋯
⋯ × max\{♯B_{t}(\underline{ε}_{1}, ⋯, \underline{ε}_{t−1})\}

This implies that:

♯\{\underline{ε} ∈ \{=, ≠\}^{G} : L\underline{ε} ≠ ∅\} ≤ ∏_{i=1}^{t} 2^{O(D(N).n)}

Since t ≤ D(N) we have the desired relation.

Proof of Theorem 2.3.- Finally, observe that the constructible subset W(N) is given as the union of some of the cells L\underline{ε}. Then, we have

deg(W(N)) ≤ ∑_{\underline{ε}} deg(L\underline{ε})

From lemma 2.4 and theorem 1.1, for every \underline{ε}, deg(L\underline{ε}) ≤ 2^{O(D(N).n)}. Moreover, the previous sum extends only on those \underline{ε}’s such that L\underline{ε} ≠ ∅. This implies, by lemma 2.5 :

deg(W(N)) ≤ 2^{O(D(N)^{2}.n)}.2^{O(D(N).n)} = 2^{O(D(N)^{2}.n)}

Taking logarithms the proof is achieved.

This lower bound only applies for acceptor networks. We can also extend it to more general arithmetic networks with arbitrary number of output gates. Assume N to be an arithmetic network that evaluates a function

ϕ = (ϕ^{A}, ϕ^{B}) : K^{n} ⟶ K^{m} × {F, T}^{ν}.

With the notations of section 1, for \underline{α} ∈ \{=, ≠\}^{m} and \underline{δ} ∈ \{F, T\}^{ν} define the constructible set:

W (\underline{α}, \underline{δ}) = \{\underline{x} ∈ K^{n} : f_{i}(\underline{x}) α_{i} 0, φ_{j}(\underline{x}) = δ_{j} for i = 1, ⋯, m and j = 1, ⋯, ν\}

From N we can construct a network N′ that accepts W (\underline{α}, \underline{δ}) such that D(N′) is in the class O(D(N) + log_{2}(m + ν)). Thus, we have

Corollary 2.6.

D(N) = Ω (\sqrt{\frac{log_{2}(sup_{\underline{α},\underline{δ}}deg(W (\underline{α}, \underline{δ})))}{n}} − log_{2}(m + ν)) .

In some particular cases, we get more precise lower bounds.

Notation 2.7. Let K be an algebraically closed field and H = {p = 0} ⊂ K^{n} a hypersurface. Let {H_{i}} be the irreducibles components of H. Denote

degg(H) = sup_{i}{deg(H_{i})}

Proposition 2.8. Let K be an algebraically closed field and N an acceptor network such that W(N) is a hypersurface. Then

D(N) ≥ log_{2}(deggW(N))

Proof: Assume that {H_{i}} are the irreducible components of W(N). The network N provides a description of W(N) as

W(N) = ⋃_{i} W_{i}

where each W_{i} is a constructible set defined by a system

p_{1,i}(x) ≠ 0, ⋯, p_{n,i}(x) ≠ 0
q_{1,i}(x) = 0, ⋯, q_{m,i}(x) = 0

Those W_{i} not containing equalities must be empty. Let

I = {i : W_{i} contains some equalities, W_{i} ≠ ∅}.

Now let us consider the polynomial

π = ∏_{1≤j≤m,i∈I} q_{j,i}.

Thus we have

W(N) = ⋃ H_{i} ⊂ {x ∈ K^{n} : π(x) = 0}.

From the irreducibility of the H_{i} it follows that for every i there is a factor of π of degree at least deg(H_{i}). Hence, the proposition follows from theorem A.

3. Lower bounds for depth over ordered fields.

In this section we shall show a lower bound for the depth of arithmetic networks, similar to that in theorem 2.3, in the case K is real closed field or K = 0 Q. The notion degree will be replaced by the number of connected components.

For the case of K real closed field we have the following lower bound:

Theorem 3.1. Let N be an acceptor network with inputs in K^{n}, where K is real closed. Then,

D(N) = Ω (\sqrt{\frac{log_{2}β_{0}(W(N))}{n}})

Proof: We follow an argumentation analogous to that of theorem 2.3. First, enumerate the set G of sign gates by pairs (i, j), the piecewise rational function associated to a sign gate (i, j) will be also denoted by f_{i,j}. Now, for \underline{ε} = (ε_{i,j}) ∈ \{>, =, <\}^{G} we denote by L\underline{ε} ⊆ K^{n} the semialgebraic subset :

L\underline{ε} := ⋂_{(i,j)∈G}\{\underline{x} ∈ K^{n} : f_{i,j} ε_{i,j} 0\}

Similarly to lemma 2.4 above, we can show :

Lemma 3.2. Under the above notations there are rational functions h_{i,j} : K^{n} ⟶ K, such that :

L\underline{ε} := ⋂_{(i,j)∈G}\{\underline{x} ∈ K^{n} : h_{i,j} ε_{i,j} 0\}

and h_{i,j} can be computed by an arithmetic circuit of depth ≤ D(N).

An analogous argumentation to that of lemma 2.5, but using now lemmas 3.2 and 1.2 along the proof, will yeald the following:

Lemma 3.3. Under the above notations :

♯\{\underline{ε} ∈ \{>, =, <\}^{G} : L\underline{ε} ≠ ∅\} ≤ 2^{O(D(N)^{2}.n)}

Proof of Theorem 3.1.- Once again observe that the semialgebraic set W(N), of those inputs accepted by N is a union of some of the semialgebraic cells L\underline{ε}. Since, because of lemma 3.2 and Kung’s theorem, β_{0}(L\underline{ε}) ≤ 2^{O(D(N).n)}, we conclude:

β_{0}(W(N)) ≤ ∑_{\underline{ε}} β_{0}(L\underline{ε}) ≤ 2^{O(D(N)^{2}.n)}.2^{O(D(N).n)} = 2^{O(D(N)^{2}.n)}

and, taking logarithms, we have the wanted lower bounds.

As in section 2 we can obtain a lower bound for the general case of arithmetic networks over real closed fields: assume N an arithmetic network with inputs in K^{n}, K real closed, m arithmetic output gates and ν boolean output gates. For \underline{α} ∈ \{>, =, <\}^{m} and \underline{δ} ∈ \{T, F\}^{ν} define the semialgebraic set W (\underline{α}, \underline{δ}) as in corollary 2.6. Thus, we have

Corollary 3.4.

D(N) = Ω (\sqrt{\frac{log_{2}(sup_{\underline{α},\underline{δ}}β_{0}(W (\underline{α}, \underline{δ})))}{n}} − log_{2}(m + ν)) .

For acceptor networks over the rationals we show two lower bounds. The first one imposes some restrictions on the kind of accepted sets, while the second one holds for the general case. For a subset W ⊆ 0 Q^{n} definable over 0 Q by a quantifier free first order formula, we shall denote by (W)_{IR} the semialgebraic subset of IR^{n} defined by the same formula. In particular, given an acceptor network N over 0 Q, by W(N)_{IR} we denote the semialgebraic subset defined by the formula obtained from the network N.

For a subset W ⊆ IR^{n}, \overline{W} and W^{∘} will be respectively the closure in IR^{n} and the interior of W. If W is semialgebraic, \overline{W} and W^{∘} are also semialgebraic. As a new parameter, we define β(W) for a subset W of 0 Q^{n} as the number of connected components with non-empty interior of the euclidean closure \overline{W} in IR^{n}. With these notations we have the following

Theorem 3.5 Let N be an acceptor network over the rationals with inputs in 0 Q^{n}. We have:

i) D(N) = Ω (\sqrt{\frac{log_{2}β_{0}((W(N))_{IR}^{∘})}{n}})
ii) D(N) = Ω (\sqrt{\frac{log_{2}β(W(N))}{n}})

Proof: Notations are those in theorems 2.3 and 3.1. First of all, observe that W(N) is a union of some definable subsets of 0 Q^{n} of the form:

L\underline{ε} := \{\underline{x} ∈ 0 Q^{n} : f_{i,j} ε_{i,j} 0, for (i, j) ∈ G\}

where \underline{ε} ∈ \{>, =, <\}^{G}. Observe that (L\underline{ε})_{IR} ⊆ IR^{n} is the corresponding semialgebraic subset produced by the network N when accepting inputs from IR^{n}. From lemmas 3.2 and 3.3 we conclude:

− β_{0} ((L\underline{ε})_{IR} ) ≤ 2^{O(D(N).n)}
− ♯\{\underline{ε} : L\underline{ε} ≠ ∅\} ≤ ♯\{\underline{ε} : (L\underline{ε})_{IR} ≠ ∅\} ≤ 2^{O(D(N)^{2}.n)}

Moreover, define E as the set of sign conditions \underline{ε} = (ε_{i,j}) ∈ \{>, <\}^{G} ⊆_{|} \{>, =, <\}^{G}. Observe that ♯\{\underline{ε} ∈ E : L\underline{ε} ≠ ∅\} ≤ 2^{O(D(N)^{2}.n)}. We have the following lemmas :

Lemma 3.6.

β_{0} (W(N)_{IR}^{∘}) ≤ ∑_{\underline{ε}∈E} β_{0} ((L\underline{ε})_{IR} ) .

Proof: First of all observe that:

⋃_{\underline{ε}∈E}(L\underline{ε})_{IR} ⊆ (W(N))_{IR}^{∘}

Observe that L\underline{ε} and (W(N))_{IR}^{∘} are semialgebraic open sets, their connected components are also open semialgebraic. Since L\underline{ε} ⊆ (W(N))_{IR}^{∘}, for every pair C and C′ of connected components respectively of L\underline{ε} and (W(N))_{IR}^{∘}, the following holds:

If C ∩ C′ ≠ ∅ , then C ⊆ C′ (3.6.1)

On the other hand, for every connected component C′ of W(N)_{IR}^{∘} we have:

C′ = ⋃_{\underline{ε}∈\{>,=,<\}^{G}} (C′ ∩ (L\underline{ε})_{IR} )

and since the above is a partition in semialgebraic sets − recall that the dimension of a union of semialgebraic sets agrees with the maximum of all the dimensions of the pieces − there is some \underline{ε} such that

dim(C′) = dim (C′ ∩ (L\underline{ε})_{IR} )

Since the set C′ is open and since algebraic sets have empty interior, then \underline{ε} ∈ E. This implies that C′ intersects at least one connected component C of some (L\underline{ε})_{IR} , \underline{ε} ∈ E. From (3.6.1) C′ contains C and the proof is achieved.

Lemma 3.7.

β(W(N)) ≤ ∑_{\underline{ε}∈E} β(L\underline{ε}).

Proof: It will be enough to show that every connected component C with non-empty interior of the closure of W(N) in IR^{n} , \overline{W(N)}, contains one connected component of \overline{L}\underline{ε} with non-empty interior for some \underline{ε} ∈ E (this is a similar argument to that in [24]). In order to see this, let us take C as before. Since C has non-empty interior, we can choose an open ball B contained in C. Now, we have

B = ⋃_{ε} B ∩ \overline{L}\underline{ε}

Observe that if \underline{ε} ∉ E, \overline{L\underline{ε}} is contained in an algebraic set and if \underline{ε} ∈ E, the set \overline{L\underline{ε}} is semialgebraic because it coincides with \overline{(L\underline{ε})_{IR}} . Since B is open and semialgebraic there must be some \underline{ε} ∈ E such that dim(B) = n = dim(B ∩ \overline{L}\underline{ε}). Then, there is a connected component C′ of \overline{L}\underline{ε} with non-empty interior meeting B. This implies that C′ must be completely contained in C.

Proof of theorem 3.5 : From lemma 3.6 the following inequalities prove statement i):

β_{0} ((W(N)_{IR}^{∘}) ≤ ∑_{\underline{ε}∈E} β_{0} ((L\underline{ε})_{IR} ) ≤ 2^{O(D(N)^{2}.n)}.2^{O(D(N).n)}

As for ii), given \underline{ε} ∈ E, (L\underline{ε})_{IR} is open, its rational points (i.e L\underline{ε}) are dense. Thus we have

β(L\underline{ε}) ≤ β_{0}(\overline{L\underline{ε}}) ≤ β_{0}((L\underline{ε})_{IR} )

and we have the inequality that achieves the proof:

β(W(N)) ≤ ♯\{\underline{ε} ∈ E : L\underline{ε} ≠ ∅\} × max\{β_{0}(L\underline{ε}) : \underline{ε} ∈ E\} = 2^{O(D(N)^{2}.n)}

Observe that the parameter used in statement i) of theorem 3.5 depends on the network and it is not an invariant of the accepted set W(N) ⊆ 0 Q^{n} . For instance, consider the open disk D = {(x, y) ∈ IR^{2} : x^{2} + y^{2} − 1 < 0} and its rational points D_{1} = D ∩ 0 Q^{2}. The number of connected components of the interior of any open semialgebraic set W ⊆ IR^{2} whose intersection with 0 Q^{2} is D_{1} is variable: simply consider any finite collection of lines r_{n} := {y = π_{n}.x} passing through the origin. If the values π_{n} are trasdendental real numbers the open semialgebraic set D \ (∪_{n=1}^{k}r_{n}) intersects the rationals in D_{1} but it has more than k + 1 connected components.

However under some conditions we can use parameters independent of the network :

Corollary 3.8. With the same notations of theorem 3.5, let W be an open semialgebraic subset of IR^{n} such that 0 Q^{n} \ W is dense in IR^{n} \ W and W ∩ 0 Q^{n} = W(N). Then,

D(N) = Ω (\sqrt{\frac{log_{2}β_{0}(W)}{n}})

Proof: In order to proof this lower bound, we shall proof the following statements:

− (W(N))_{IR}^{∘} ⊆ W.
− β_{0}(W) ≤ β_{0} ((W(N))_{IR}^{∘}).

For a point \underline{x} in IR^{n} \ W there is a sequence of rational points in 0 Q^{n} \ W converging to it. Since W ∩ 0 Q^{n} = W(N), this sequence is in 0 Q^{n} \ W(N) ⊆ IR^{n} \ W(N). Thus, we conclude that \underline{x} ∈ \overline{IR^{n} \ W(N)} = IR^{n} \ (W(N))_{IR}^{∘} and we have the first assertion. For the second assertion observe that W and (W(N))_{IR}^{∘} are both open semialgebraic, and since (W(N))_{IR}^{∘} ⊆ W, for every pair of connected components C and C′ respectively of (W(N))_{IR}^{∘} and W, the property (3.6.1) holds. Now assume there is a connected component C′ of W with empty intersection with any connected component of (W(N))_{IR}^{∘}. This implies that C′ ⊆ \overline{IR^{n} \ (W(N))_{IR}} . However, C′ ∩ 0 Q^{n} does not intersect IR^{n} \ (W(N))_{IR} and rational points are dense in any open set, which implies that C′ is completely included in the boundary ∂(W(N))_{IR} . Thus, we have arrived to a contradiction since the boundary of a semialgebraic set has always empty interior. We conclude that every connected component of W contains at least one of (W(N))_{IR}^{∘} and we have the second assertion.

For an arithmetic network N, with inputs in 0 Q^{n}, m arithmetic output nodes and ν boolean output nodes we have the lower bound:

Corollary 3.9.

D(N) = Ω (\sqrt{\frac{log_{2}(sup_{\underline{α},\underline{δ}}β(W (\underline{α}, \underline{δ})))}{n}} − log_{2}(m + ν)) .

where W (\underline{α}, \underline{δ}) is defined in 0 Q^{n} for \underline{α} ∈ \{>, =, <\}^{m} and \underline{δ} ∈ \{T, F\}^{ν} as in corollaries 2.6 and 3.4.

4. Applications.

In this last section we shall see that the general lower bounds obtained for the depth in previous sections imply the inefficiency of arithmetic networks with respect to the parallel complexity of a series of natural problems. In order to achieve this purpose we shall introduce some notations and classes of languages acceptable by networks.

Let K be a field, for an element \underline{x} ∈ K^{∗} we denote by | \underline{x} | the length of the element, i.e. the subindex of the last non-zero coordinate of \underline{x}. For a language L ⊆ K^{∗} we shall denote by L_{n} the set of elements of length n :

L_{n} := \{\underline{x} ∈ L :| \underline{x} |= n\}

Definition 4.1 For a field K the class NC_{K}(non−uniform) is the class of all those languages L ⊆ K^{∗} such that there is a sequence {N_{n}}_{n∈IN} of acceptor networks over K verifying :

− Size of N_{n} is polynomial in n. − D(N_{n}) is poly-logarithmic in n. − W(N_{n}) = L_{n}.

We call a polynomial time arithmetic decision problem L ⊆ K^{∗} well-parallelizable if L ∈ NC_{K}(non − uniform). We visualize in Fig. 3 the classes and problems we are going to analyze:

Field  Sequential  Parallel
K  P_{K}(non − uniform)
algebraically 2^{n}-Root NC_{K}(non − uniform)
closed  P_{K}
R  P_{R}(non − uniform)
real Real Knapsack Problem NC_{R}(non − uniform)
closed  P_{R}

Knapsack Problem

0 Q P_{0 Q} NC_{0 Q}(non − uniform)
GP_{0 Q}

Fig.3.- Table with classes and problems not well-parallelizable by acceptor networks Our purpose now will be to show that all the problems and classes on the left-hand side of the previous figure are not contained in those written on the right hand side.

4.2.- Real Knapsack problem is not well-parallelizable by acceptor networks :

NC_{IR} (non − uniform) ⊆_{|} P_{IR} (non − uniform)

Let R be a real closed field. An algebraic computation tree, see [2], [22] or [25], is a rooted binary tree, T = T (X_{1}, ⋯, X_{n}), with a finite number of nodes. Nodes are of four types: just one input node (the root of the tree, accepting \underline{x} = (x_{1}, ..., x_{n}) ∈ R^{n} as input), computation nodes (nodes with just one son where an arithmetic operation is performed), branching nodes (nodes with two sons where a sign “z_{i} μ 0?”, μ ∈ {≥, >, =}, on some precomputed z_{i} is tested) and output nodes (also called leafs, labeled with the corresponding Y ES/NO answer). The set W (T) ⊆ R^{n} of inputs reaching a YES answer, is the semialgebraic set accepted by the tree T.

The class P_{R}(non − uniform) is defined as the class of all those languages L ⊆ R^{∗} such that there is a sequence of algebraic computation trees {T_{n}}_{n∈IN} such that the height of T_{n} is polynomial in n and W (T_{n}) = L_{n}.

In order to compare this class with NC_{R}(non − uniform) we shall analyze the real Knapsack problem K = ∪_{n∈IN} K_{n} ⊆ R^{∗} defined at the Introduction. In [20] Meyer auf der Heide shows a sequence of linear search programs (i.e. algebraic computation trees involving only linear operations) solving the real Knapsack problem in non-uniform polynomial sequential time: O(n^{4}log_{2}n). This implies that real Knapsack problem is in P_{R}(non − uniform). Our previous lower bounds allow us to conclude:

Corollary 4.2.1 The parallel time of the real Knapsack problem is in Ω(\sqrt{n}), i.e. it is in P_{R}(non − uniform) \ NC_{R}(non − uniform). In particular, acceptor networks are not powerful enough to parallelize algebraic computation trees.

Proof: Consider the semialgebraic set

R^{n} \ K_{n} = {(x_{1}, ⋯, x_{n}) : ∏_{S}(∑_{i∈S} x_{i} − 1) ≠ 1}.

It was shown in [10] that the number of semialgebraic connected components of the set R^{n} \ K_{n} is at least 2^{\frac{n^{2}}{2}} , thus from theorem 3.1 we obtain an Ω(\sqrt{n}) lower bound for the parallel time of Knapsack solved by acceptor networks.

In [2] a weakened version of the real Knapsack problem is considered:

Real ε-Approximation Knapsack Problem .-

Given ε > 0 and \underline{x} = (x_{1}, ⋯, x_{n}) ∈ IR^{n} decide whether it belongs to

K_{n,ε} = \{\underline{x} ∈ IR^{n} : ∃S ⊆ \{1, ⋯, n\} such that | ∑_{i∈S} x_{i} − 1 |< ε\}

By means of our methods we obtain the following corollary Corollary 4.2.2 The real ε-approximation Knapsack problem is not in NC_{IR} (non−uniform). In fact, there is a Ω(\sqrt{n}) lower bound for parallel time of this problem.

Proof: For ε > 0 small enough the number of connected components of

IR^{n} \ K_{n,ε} := {(x_{1}, ⋯, x_{n}) : | ∑_{i∈S} x_{i} − 1 |≥ ε for all S}

is at least 2^{\frac{n^{2}}{2}} since every connected component of K_{n}^{c} contains one of R^{n} \K_{n,ε} (see Fig. 4 below). As before the corollary is a direct consequence of theorem 3.1.

\underline{4.3.-“Integer part” is not well-parallelizable}:
P_{IR} \ NC_{IR} (non − uniform) ≠ ∅

In [4] a uniformization of algebraic computation trees by real Turing machines is introduced (cf. also [7] and [23] for this uniformization). We shall follow in this subsection the notations introduced there. Thus, for a real Turing machine M and L(M) ⊆ IR^{∗} the language accepted by M, we define the running time R_{M}(\underline{x}) for \underline{x} ∈ L(M) as the number of nodes in M traversed by the computation of M on \underline{x} until it reaches the output node.

With these notations, we can define the halting time function associated to a machine M to be

\begin{matrix}T_{M} : & IN ⟶ IN ∪ \{+∞\} \\ n ↦ sup\{R_{M}(\underline{x}) : \underline{x} ∈ L(M), | \underline{x} |= n\} \end{matrix}

As defined in [4], the class P_{IR} is the class of all those languages L ⊆ IR^{∗} accepted by some real Turing machine M within halting time T_{M}(n) which is polynomial in n. We are going to show that real Turing machines are not well-parallelizable by acceptor networks. In [7] and [23] it is proved the strict inclusion P_{IR} ⊆_{|} P_{IR} (non − uniform) . In order to analyze the parallelization of problems in P_{IR} we study the computation of the “integer part” of a real number x ∈ IR: ⌊x⌋.

By means of a “binary search” one can design a real Turing machine that computes ⌊x⌋ in sequential time O(log_{2}(∥ x ∥)), where ∥ x ∥ is the absoulte value of x ∈ IR. The procedure is based on finding the “non-negative integer t ∈ IN satisfying 2^{t} ≤ x < 2^{t+1}”. This is possible in O(log_{2} ∥ x ∥) arithmetic steps. Then one continues the procedure considering x′ = x − 2^{t}.

Clearly the function ⌊x⌋ is not in P_{IR} since its time depends on the input x and not on the length of the input | x |= 1. In order to avoid this difficulty we introduce the function “integer part modulo a non-negative integer k ∈ IN”: ⌊x⌋_{k}.

⌊x⌋_{k} = \{ \begin{matrix}⌊x⌋, & if 0 ≤ x < k + 1 \\ 0, & otherwise \end{matrix}

The evaluation of this function can be easily obtained by a real Turing machine in time O(log_{2}k). Using this function we can obtain the following:

Corollary 4.3.1 There is a language I in P_{IR} \NC_{IR} (non−uniform). In particular, acceptor networks are not able to parallelize real Turing machines. Moreover, the computation of the “ integer part” is not well-parallelizable by arithmetic networks. Proof: We consider the following language I ⊆ IR^{∗}:

I := \{\underline{x} = (x_{1}, ⋯, x_{n}, ⋯) ∈ IR^{∗} : x_{i} − ⌊x_{i}⌋_{2^{n}} = 0 for i = 1, ⋯, n =| \underline{x} |, \} (1)

Observe that I can be accepted by a real Turing machine M with halting time T_{M}(n) = O(n^{2}). Thus, I ∈ P_{IR} . However, I_{n} has 2^{n^{2}} connected components and, from theorem 3.1, we conclude a Ω(\sqrt{n}) lower bound for the parallel time by acceptor networks.

Remark 4.3.2 i) Observe that the previous example can also be stated for every real closed field. ii)While this paper was written, the authors have learned that F. Cucker had also obtained an example of language lying in P_{IR} \ NC_{IR} by means of a different method (see [6]).

Corollary 4.3.3 The “Real Circuit Decision problem” and the “Problem of Deciding wether a degree d equation is Solvable by Substitution” are not in NC_{IR} (non − uniform). Proof: Both problems have been shown to be P_{IR} -complete for reductions in NC_{IR} in [8].

\underline{4.4.-Knapsack ∉ NC_{0 Q}(non − uniform)}≠ NP

The lower bounds obtained in previous sections also show the inefficiency of arithmetic networks over 0 Q to parallelize arithmetic problems. We shall begin by the rational version of the Knapsack problem as stated at the Introduction (K = 0 Q). This problem is NP-complete and the algorithm in [20] also applies to show an O(n^{4}log_{2}n) upper bound in a non-uniform model by linear search programs. We have the folowing

Corollary 4.4.1. Knapsack is not in NC_{0 Q}(non − uniform). Moreover, there is an Ω(\sqrt{n}) lower bound for the parallel time by networks. Proof: Under the notations of corollary 4.2.1, consider the set of rational points 0 Q^{n} \K_{n}. Then, IR^{n} \ K_{n} is an open semialgebraic set, its complement K_{n} has dense rational points and, applying corollary 3.8 we conclude the Ω(\sqrt{n}) wanted lower bound.

Corollary 4.4.2 The rational version of the ε-Approximation Knapsack problem has parallel complexity in Ω(\sqrt{n}). Proof: Observe that the connected components of the euclidean closure of:

0 Q^{n} \ K_{n,ε} := {(x_{1}, ⋯, x_{n}) ∈ 0 Q^{n} : | ∑_{i∈S} x_{i} − 1 |≥ ε for all S}

are exactly those of

IR^{n} \ K_{n,ε} := {(x_{1}, ⋯, x_{n}) ∈ IR^{n} : | ∑_{i∈S} x_{i} − 1 |≥ ε for all S}

since the rational points are dense in K_{n,ε} and for ε > 0 small enough all the connected components of this set have non-empty interior (see [2] and Fig. 4 below). This implies by theorem 3.5, ii) the Ω(\sqrt{n}) wanted lower bound.

Fig.4.- The ε-Approximation Knapsack Problem for n = 2

4.5.-“Integer part” over 0 Q is not well-parallelizable :

P_{0 Q} ⋂ GP_{0 Q} \ NC_{0 Q}(non − uniform) ≠ ∅

The general theory of real closed fields has no other measure of the cost of an operation than the unit cost. For the field of rationals there are two different forms of measuring the inputs and the cost of the operations along a procedure: the uniform and the logarithmic (in the terminology of [1]).

We shall consider the algorithmic model of rational Turing machines (see [4]) which is polynomially equivalent to the model of rational RAMs.

The height of a rational number x ∈ 0 Q is max{log_{2} | p |, log_{2} | q |}, where p and q are coprime integers and x = \frac{p}{q}. The size of an element \underline{x} ∈ 0 Q^{∗}, size(\underline{x}), is the sum of its length, | \underline{x} |, plus the maximum of the heights of its coordenates.

The cost (logarithmic cost) of a rational Turing machine M, over 0 Q, on input \underline{x}, C_{M}(\underline{x}), is the product of the time, T_{M}(\underline{x}), and the maximum of the heights of the intermediate values along the computation on input \underline{x} until the machine halts. Under these conventions we can introduce the following notions Definition 4.5.1 (cf. [1] and [4]) The class P_{0 Q} is the class of all arithmetic problems L ⊆ 0 Q^{∗}, accepted by a rational Turing machine, M, within cost, C_{M}(\underline{x}), polynomial in the input size, O(size(\underline{x})^{k}).

Definition 4.5.2 (cf. [19]) The class GP_{0 Q} (genuinely polynomial time over 0 Q) is the class of all arithmetic problems over 0 Q accepted by a rational RAM within time (uniform cost), T_{M}(\underline{x}), polynomial in the input length, O(| \underline{x} |^{k}).

Corollary 4.5.3 There is a language I_{ε} in P_{0 Q} ∩GP_{0 Q} which is not in NC_{0 Q}(non−uniform). Moreover, the computation of the “integer part” of a rational number cannot be well-parallelizable by networks. In particular, acceptor networks are not very accurate to parallelize rational Turing machines and rational RAMs. Proof: We consider the following semialgebraic sets:

I_{n,ε} := {(x_{1}, ⋯, x_{n}) ∈ 0 Q^{n} : 0 ≤ x_{i} − ⌊x_{i}⌋_{2^{n}} ≤ ε, i = 1, ⋯, n}

Now define the language I_{ε} = ∪_{n∈IN} I_{n,ε}. A procedure analogous to that sketched in corollary 4.3.1 for the reals, holds to compute the integer part of all the coordinates a rational input \underline{x} = (x_{1}, ⋯, x_{n}, ⋯) ∈ 0 Q^{∗}: ⌊x_{i}⌋_{2^{n}}, n=| \underline{x} |. These values are computed in time polynomial in | \underline{x} | and in polynomial cost in size(\underline{x}). Thus, I_{ε} is both in P_{0 Q} and GP_{0 Q}. However, the euclidean closure in IR^{n} of I_{ε,n} has exactly 2^{n^{2}} connected components with non-empty interior. Thus theorem 3.5, ii) implies an Ω(\sqrt{n}) lower bound and I_{ε} is not in NC_{0 Q}(non − uniform). The other assertions are immediate.

Observe that P_{0 Q} ⊆ P, where P is the class of polynomial time accepted languages by a Turing machine. Then, P contains an arithmetic problem which is not in NC_{0 Q}(non − uniform). In particular, acceptor networks are not efficient to parallelize Turing machines.

4.6.-For algebraically closed fields :

P_{K} \ NC_{K}(non − uniform) ≠ ∅

Let now K be an algebraically closed field. We show now that acceptor networks are not able to parallelize efficiently polynomial time arithmetic problems over K. As in the real closed case we consider two sequencial classes: P_{K}(non − uniform) and P_{K}.

First, let us consider the model given by Turing machines over K (as in [4]). The class P_{K} is defined as the class of decision problems L ⊆ K^{∗} accepted by a Turing machine over K, M, such that the time T_{M}(\underline{x}) is polynomial in the input length : O(| \underline{x} |^{k}).

Let us observe that for any language L in P_{K}, the subset L_{n} ⊆ K^{n} is constructible and definable over a finitely generated field extension of the prime field of K.

We also have the non-uniform sequential model given by algebraic computation trees over K. They are defined as in 4.2 but their branching nodes only test sign conditions in {=, ≠}. In [13] or [15] they are also called binary tree decisional programs.

Now we define the class P_{K}(non − uniform) of all those languages L ⊆ K^{∗} such that there is a sequence {T_{n}}_{n∈IN} of algebraic computation trees over K verifying:

− For every n ∈ IN, T_{n} solves L_{n}.

− The height of T_{n} is polynomial in n. Observe that P_{K} ⊆_{|} P_{K}(non − uniform) .

Corollary 4.6.1 There is a language R in P_{K} which is not in NC_{K}(non − uniform). In particular, acceptor networks are not able to parallelize arithmetic problems solvable in polynomial time by decisional binary tree programs or Turing machines over K.

Proof: Let q be a prime number different to the characteristic of K. Define the following language which is an extension to n variables of 2^{n}-Root:

R := \{\underline{x} = (x_{1}, ⋯, x_{n}, ⋯) ∈ K^{∗} : (x_{i})^{q^{n}} − 1 = 0 for i = 1, ⋯, n =| \underline{x} |\}

By iteration of the q-th power operation, one can define a Turing machine over K that accepts R in time O(| \underline{x} |^{2}).

However, for every n ∈ IN the constructible set R_{n} ⊂ K^{n} has degree q^{n^{2}} which from theorem 2.3 leads to an Ω(\sqrt{n}) lower bound and it is not in NC_{K}(non − uniform).

4.7.- Lower bounds for quantifier elimination. Assume K a real closed or algebraically closed field. When speaking about K we consider the first order language L together with the non-logic symbols “{0, 1}, +, −, ×, =”. In the real closed case one also includes the relational symbol “>” (see [9] and [11] for the complete details). The theorems in section 1 allow us to simplify the results of the last mentioned authors:

Corollary 4.7.1. The quantifier elimination in the elementary theory of K is simply exponential in parallel time.

Proof: First consider the case of K real closed. By [9] proposition 2 one can construct a sequence of formulae ϕ_{k}(X, Y), k = 0, 1, ⋯ with the following properties:

− The defining polynomials of ϕ_{k} have coefficients in 0 Q.

− The size of the formula ϕ_{k}is in O(k).

− The formula ϕ_{k} defines the set M_{k} of the 2^{2^{k}}-th roots of the unit in the complex plane K[i] = C.

Assume θ a quantifier free formula equivalent to ϕ_{k}. In particular θ defines M_{k}. This implies that any machine working in parallel (under the conventions in [11]) that writes θ must contain an arithmetic network that recognizes the set M_{k}. This last set has exactly 2^{2^{k}} semialgebraic connected components and the result follows from theorem 3.1.

For the case K is algebraically closed one follows [16] to construct a sequence of formulae ψ_{k}, k = 1, 2, ⋯ free in the variables X, Y with coefficients in 0 Q and size in O(k) such that each ψ_{k}

defines the graph M_{k} of the map K → K that sends x onto x^{2^{2^{k}}}. The result is concluded once we apply theorem 2.3 to any machine working in parallel that writes a formula \overline{θ} equivalent to ψ_{k} (one makes Y = 1 to get the result).

Acknowledgment. The authors would like to thank Joos Heintz for suggesting the application of the lower bounds in sections 2 and 3 to simplify the analysis of the parallel time of quantifier elimination.

References.

[1] A. Aho, J. Hopcroft and J. Ullman.The Design and Analysis of Computer Algorithms .Addison-Wesley, 1976

[2] M. Ben-Or. “Lower bounds for algebraic computation trees”. A.C.M. 15^{th} Symp. on Theory of Computing, pp.80-86, 1983.

[3] R. Benedetti and J.J. Risler. Real algebraic and semialgebraic sets. Hermann, Paris, 1990.

[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 Amer. Math. Soc., vol.21, n.1, pp.1-46, 1989.

[5] J. Bochnak, M. Coste and M.-F. Roy. Géométrie algébrique réelle. Ergebnisse der Math., 3.Folge, Band 12, Springer Verlag, 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”. To appear in Int. J. of Algebra and Comp..

[8] F. Cucker and A. Torrecillas. “Two P-complete problems in the theory of the reals”. To appear in Proceedings of ICALP’91, Madrid, (1991).

[9] J.H. Davenport, J. Heintz. “Real quantifier elimination is doubly exponential”. J. of Symbolic Computation 5, Academic Press, (1988), 29-36.

[10] D.P. Dobkin, R.J. Lipton. “A lower bound of \frac{1}{2}n^{2} on linear search programs for solving the Knapsack problem”. JCSS, 18, pp. 86-91, 1976.

[11] 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).

[12] J. Von zur Gathen. “Parallel arithmetic computations: a survey”. Mathematical Foundations on computer Science, 13th. Proc. MFCS, 1986, 1986.

[13] J. von zur Gathen. “Algebraic Complexity Theory”. Technical Report of the Department of Computer Science. University of Toronto, 1988

[14] D. Grigor’ev. “Complexity of deciding Tarski algebra”. J. of Symb. Comp., 5 pp.65-108, 1988.

[15] D. Grigorév; “Lower bounds in algebraic computational complexity”. Journal of Soviet Mathematics , 4., pp.1388-1425, 1985.

[16] J. Heintz. “Definability and fast quantifier elimination over algebraically closed fields”. Theor. Comp. Science 24, pp. 239-278, 1983. CORRIGENDUM in Theor. Comp. Science 39, p. 343, 1985.

[17] J. Heintz, M.-F. Roy and P. Solerno. “Sur la Complexité du Principe de Tarski-Seidenberg”. Bull. Soc. Math. de France 118, pp. 101-126,1990.

[18] H.T. Kung. “New algorithms and lower bounds for the parallel evaluation of certain rational expressions and recurrences”. J. of the ACM, 23, pp. 534-543, 1976.

[19] F. Meyer auf der Heide. “On genuinely time bounded computations”. Symp. Theor. Aspects of Comp., LNCS 349, pp.1-16, Springer Verlag, 1989.

[20] M. Meyer auf der Heide. “A Polynomial Linear Search Algorithm for the n-dimensional Knapsack Problem”. J. of the ACM, vol. 31, No. 3, pp. 668-676,1984.

[21] J. Milnor. “On the Betti numbers of real algebraic varieties”. Proc. AMS, 15, pp.275-280, 1964.

[22] J.L. Montaña, L.M. Pardo and T. Recio. “The non-scalar model of complexity in computational geometry”. Proc. of MEGA’90, Progress in Math. 94. Birkhauser, pp. 347-362,1991.

[23] J.L. Montaña.“Cotas inferiores en teoría de la complejidad algebraica”. Doctoral Thesis. Universidad de Cantabria, 1992.

[24] L.M. Pardo, T. Recio. “Arboles algebraicos: un modelo de computación en geometría”. Contribuciones Científicas, pp. 241-248, Universidad de Cantabria, 1988.

[25] M. Rabin; “Proving simultaneous positivity of linear forms” J. of Comp. and Syst. Sc., 6, pp.639-650, 1972.

[26] S. Smale. “On the topology of algoritms”. I, J. Complexity, 3, pp. 81-89, 1987.

[27] V. Strassen; “Algebraic Complexity Theory”. Hand Book of Theoretical Computer Science, capítulo 11, pp. 634-671, 1990.