COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES WITH ELEMENTARY TRANSCENDENTAL FUNCTION GATES

D. Grigoriev and N. Vorobjov Departments of Computer Science and Mathematics Penn State University, University Park, PA 16802, USA dima@cse.psu.edu vorobjov@cse.psu.edu

Abstract. We consider computation trees which admit as gate functions along with the usual arithmetic operations also algebraic or transcendental functions like exp, log, sin, square root (defined in the relevant domains) or much more general, Pfaffian functions. A new method for proving lower bounds on the depth of these trees is developed which allows to prove a lower bound Ω(\sqrt{log N}) for testing membership to a convex polyhedron with N facets of all dimensions, provided that N is large enough.

I. Pfaffian Computation Trees.

Definition 1. By a Pfaffian computation tree T we mean a generalization of an algebraic decision tree (see e.g. [1, 4, 12, 28, 29, 30]) in which at any node v of T a Pfaffian function f_{v} in the variables X_{1}, …, X_{n} (see the definition A2 in the Appendix) is attached, which satisfies the following properties. Let f_{v_{0}}, …, f_{v_{ℓ}}, f_{v_{ℓ+1}} = f_{v} be the functions attached to all the nodes along the branch T_{v} of T leading from the root v_{0} to v. We assume that Pfaffian function f_{v} satisfies the following differential equation

df_{v} = ∑_{1≤j≤n}g_{v,j}(X_{1}, …, X_{n}, f_{v_{0}}, …, f_{v_{ℓ}}, f_{v})d X_{j}

with g_{v,j} ∈ ℝ[X_{1}, …, X_{n}, U_{0}, …, U_{ℓ+1}]. The tree T branches at v to its three sons according to the sign of f_{v} (cf. [1]). Thereby, to each node v one can naturally assign a semi-Pfaffian set U_{v} ⊂ ℝ^{n} (see the definition A3 in the Appendix) consisting of all the points for which the sign conditions for functions along the branch T_{v} are valid. Thus, to three sons of v one assigns the semi-Pfaffian sets U_{v} ∩ {f_{v} > 0},

Typeset by AMS-TEX 2 D. GRIGORIEV AND N. VOROBJOV

U_{v} ∩ {f_{v} = 0}, U_{v} ∩ {f_{v} < 0}, respectively. We assume that f_{v} is defined on a certain domain (see the definition A2) containing U_{v}. To any leaf of T an output either “yes” or “no” is assigned and we say that T tests the membership problem to the set of all points (x_{1}, …, x_{n}) ∈ ℝ^{n} for which the outputs of the corresponding leaves of T are “yes” (see [1]).

Note that a more general notion of a Pfaffian sigmoid was introduced in [10] and a method for obtaining lower bound on the (parallel) complexity was developed.

If we take only arithmetic operations as the gate Pfaffian functions f_{v} in T then we come to the algebraic computation trees (see e.g. [1]). As examples of gate Pfaffian functions f_{v} one could take exp (f_{v_{q}}), log(f_{v_{q}}), where log is defined on the positive half-line, \sqrt{f_{v_{q}}}, where square root is defined on the positive half-line, sin(f_{v_{q}}), where sin is defined on the interval (−π, π), tan(f_{v_{q}}), where tan is defined on the interval (−π/2, π/2), 0 ≤ q ≤ ℓ. Other examples one can find in section A1 of the Appendix. Trees T restricted to some special classes of Pfaffian functions (for instance, the mentioned above) can be of a particular interest, but since we are interested in the complexity lower bounds we shall consider arbitrary Pfaffian functions.

Suppose that the degrees deg g_{v,j} of the polynomials occurring in the definition of the gate functions f_{v} in T , are less than d.

Now we are able to formulate the main result of the paper. This result was annownced in [15]. Theorem. Let a Pfaffian computation tree T test a membership problem to a closed convex polyhedron P ⊂ ℝ^{n}, having N facets of all the dimensions. Then the depth K of T is greater than Ω(\sqrt{log N}), provided that N ≥ (dn)^{Ω(n^{4} log d)}.

In [11] a particular case of the theorem for n = 2, so when P is a polygon, was proved.

Several methods based on topological characteristics are known for obtaining complexity lower bounds for algebraic computation trees testing membership to

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 3

a semialgebraic set S ⊂ ℝ^{n}. In [1], the bound Ω(log C) was proved, where C is the number of connected components of S or its complement, in [3,4,28] the bound Ω(log χ) was proved, where χ is the Euler characteristics. The most general (among the listed) bound Ω(log B) was proved in [3,29], where B is the sum of Betti numbers of S.

Actually one could directly extend these results to Pfaffian computation trees, replacing in the proofs the references to Milnor’s bound [23] on the sum of Betti numbers of a semialgebraic set by the references to Khovanskii’s bound [20] for the sum of Betti numbers of a semi-Pfaffian set. This leads to the following proposition [11]. If a Pfaffian computation tree tests the membership problem to a semi-Pfaffian set W with the sum of Betti numbers B, then the depth of the tree is greater than Ω(\sqrt{log B}) [11].

There is a conjecture that the bound in [20] could be improved (see the section A1 in the Appendix). This conjecture implies the lower bounds Ω(log N) in the theorem and Ω(log B) in the proposition from [11] respectively.

Observe that as the sum of Betti numbers of a convex polyhedron equals to 1, the theorem does not follow, apparently, from the proposition. Note that in [12] the complexity lower bound Ω(log N) was proved for testing membership to a polyhedron with N facets by an algebraic decision tree (for large enough N, cf. the theorem). In [30] a similar bound was shown for a weaker model of linear decision trees. The method from [12] cannot be directly generalized to Pfaffian computation trees, since in [12] the efficient quantifier elimination procedure for the first-order theory of reals (see [9, 14, 17, 24]), was essentially used whereas for the theories involving Pfaffian functions (in particular, elementary transcendental), the quantifier elimination does not exist.

We remark that the computations involving other functions, rather than arithmetic, were considered in several papers: in [18] for the computations involving root extractions a lower bound for computing an algebraic function was obtained,

4 D. GRIGORIEV AND N. VOROBJOV

in [13] this result was extended for the computations involving exp and log.

We mention that for testing membership to a polyhedron an upper bound O(log N)n^{O(1)} was shown in [22] even for linear decision trees.

Now we proceed to the proof of the theorem which will continue up to the end of section III.

We start with introducing some necessary concepts and notations. In section II we introduce the notion of i-angle points and prove that the set of i-angle points has the dimension at most i. This notion differs from the concept of sharp points introduced and used in [12], the latter does not work for Pfaffian computation trees. In section III we introduce and study another important technical concept, flat points. All necessary information about Pfaffian functions and sub-Pfaffian sets we included in the Appendix (in which the numbering of all the statements, definitions and sections begins with A).

For an m-plane Q ⊂ ℝ^{n} and a point x ∈ ℝ^{n} denote by Q(x) the m-plane, collinear to Q and containing x. For a facet Π of the polyhedron P denote by \overline{Π} the dim(Π)-plane, containing Π (we assume a facet to be open, i.e. without its boundary).

Two planes Q_{1}, Q_{2} or arbitrary dimensions are called transversal if

dim(Q_{1}(0) ∩ Q_{2}(0)) = max{0, dim(Q_{1}(0)) + dim(Q_{2}(0)) − n}

The proofs of the following two easy lemmas one can find in [12] (lemma 1 is also proved in [5]). Lemma 1. For each j with 1 ≤ j ≤ n there exists a family A_{j} consisting of j(n − j) + 1 j-subspaces in ℝ^{n} such that for any i-subspace Q ⊂ ℝ^{n}, 1 ≤ i ≤ n there is a j-subspace R ∈ A_{j} which is transversal to Q. Lemma 2. There exists a rotation of coordinates X_{1}, …, X_{n} such that after this rotation for every j, every Q ∈ A_{j} and for every facet Π of P, the subspace Q and the plane \overline{Π} become transversal.

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 5

In what follows we suppose that the coordinate system meets the requirements of lemma 2. Now we reduce consideration to the case when the polyhedron P is bounded. The next construction follows the beginning of the proof of lemma 5 [12].

Let t be the minimal dimension of facets of P. Fix a certain t-facet P_{t} of P, then t-plane \overline{P}_{t} is contained in P. On each facet Π of P choose a point x_{Π} ∈ Π. Take an arbitrary hyperplane σ transversal to \overline{P}_{t} and such that the points x_{Π} for all facets Π of P lie in the same of two open half-spaces of ℝ^{n} ∖ σ (denote this half-space by Σ). Consider the polyhedron P ∩ (Σ ∪ σ), it contains a facet of a dimension less than t. Continuing this process while t ≥ 1, we come eventually to the case t = 0, i.e., polyhedron P′ obtained as a result of this process has a vertex.

There exists a linear form L = β_{1}X_{1} + ⋯ + β_{n}X_{n} with β_{i} ∈ ℝ, 1 ≤ i ≤ n such that for every γ ∈ ℝ an intersection P′′ = {L + γ ≥ 0} ∩ P′ is compact. Take γ such that x_{Π} ∈ {L + γ ≥ 0} ∩ P′ for all Π.

In order to reduce consideration to the compact polyhedron P′′, observe that from a Pfaffian computation tree of depth K for the membership problem to P, one can easily produce a Pfaffian computation tree of a depth at most K +n for the membership problem to P′′. Assuming that the theorem is valid for the compact P′′, and thus K + n ≥ Ω(\sqrt{log N}), we get a similar bound K ≥ Ω(\sqrt{log N}) under the supposed in the hypothesis of the theorem inequality for N. Therefore, in what follows we assume that P is bounded.

In section A2 a sequence

ℝ = ℝ_{0} ⊂ ℝ_{1} ⊂ ℝ_{2} ⊂ ⋯

of nonstandard extensions of fields is introduced. One can choose in each ℝ_{i+1} an element infinitesimal relative to ℝ_{i}. We denote these elements, respectively, by

ϵ_{1} ∈ ℝ_{1}, {δ_{ℓ}^{(j)} ∈ ℝ_{(ℓ−1)(n^{2}+1)+j+1} : 1 ≤ ℓ ≤ n − 1, 1 ≤ j ≤ n^{2} + 1},

ϵ_{2} ∈ ℝ_{n^{3}−n^{2}+n+1}, ϵ_{3} ∈ ℝ_{n^{3}−n^{2}+n+2} (the reason for these notations would become clear later on). To match the notations denote the fields ℝ_{1} = ℝ_{ϵ_{1}}, ℝ_{(ℓ−1)(n^{2}+1)+j+1} =

6 D. GRIGORIEV AND N. VOROBJOV

ℝ_{δ_{ℓ}^{(j)}}, 1 ≤ ℓ ≤ n − 1, 1 ≤ j ≤ n^{2} + 1, ℝ_{n^{3}−n^{2}+n+1} = ℝ_{ϵ_{2}}, ℝ_{n^{3}−n^{2}+n+2} = ℝ_{ϵ_{3}}, respectively. For brevity set also ℝ_{δ} = ℝ_{n^{3}−n^{2}+n} = ℝ_{δ_{n−1}^{(n^{2}+1)}}. The completion (see section A2) for any sub-Pfaffian set U (see the definition A4) we denote by U^{(δ)} = U^{(n^{3}−n^{2}+n)}, U^{(ϵ_{3})} = U^{(n^{3}−n^{2}+n+2)}. Analogously we denote the languages (see the section A2) L_{δ} = L_{n^{3}−n^{2}+n}, L_{ϵ_{2}} = L_{n^{3}−n^{2}+n+1}, L_{ϵ_{3}} = L_{n^{3}−n^{2}+n+2}. In the section A2 for each i the standard part st_{i} is described. Actually, throughout the paper we’ll use almost in all the cases st_{n^{3}−n^{2}+n} which we’ll for brevity denote by st (on occasions we’ll use also st_{n^{3}−n^{2}+n+1} which we denote by st_{ϵ_{2}}).

Consider a Pfaffian computation tree T testing the membership to P with depth K. Fix any its branch with the output “yes”, and let f_{v_{0}}, …, f_{v_{K}} be the Pfaffian functions attached to the nodes along this branch. We rename the functions ±f_{v_{0}}, …, ±f_{v_{K}} by u_{0}, …, u_{K} in such a way that u_{0}, …, u_{K_{1}} for a certain K_{1} ≦ K, correspond to the sign zero, and u_{K_{1}+1} > 0, …, u_{K} > 0 correspond to nonzero signs along the branch. More precisely, consider a semi-Pfaffian set (see the definition A3)

W = {x ∈ ℝ_{ϵ_{3}}^{n} : u_{0}(x) = ⋯ = u_{K_{1}}(x) = 0, u_{K_{1}+1}(x) > 0, …, u_{K}(x) > 0}.

which is the accepting set corresponding to the branch. Then the set W ∩ ℝ^{n} is the set of points on which T along the fixed branch outputs “yes”, hence W ∩ ℝ^{n} ⊂ P. Since the functions u_{0}, …, u_{K} are defined over ℝ, the completion (see the section A2) (W ∩ ℝ^{n})^{(ϵ_{3})} = W. In the sequel we’ll estimate the number of i-facets Π of P such that dim(W ∩ Π ∩ ℝ^{n}) = i.

When K_{1} < 0 the set (W ∩ℝ^{n}) lies in the interior of P, so this estimate is trivial. Therefore, we assume that K_{1} ≥ 0 and denote f = u_{0}^{2} + ⋯ + u_{K_{1}}^{2}.

II. Angle Points.

Definition 2. A point x ∈ W is called a 0-quasiangle if u_{K_{1}+1}(x) ≥ ϵ_{1}, …, u_{K}(x) ≥ ϵ_{1}, and there exist points y_{1}, …, y_{n} ∈ {f −ϵ_{3} = 0} such that the Euclidean distances ∥y_{i} − x∥ ≤ ϵ_{2}, 1 ≤ i ≤ n and

(det | \begin{matrix}\frac{∂f}{∂X_{1}} (y_{1}) & … \frac{∂f}{∂X_{n}} (y_{1}) \\ ⋮ & ⋮ \\ \frac{∂f}{∂X_{1}} (y_{n}) & … \frac{∂f}{∂X_{n}} (y_{n}) \end{matrix} | )^{2} > ϵ_{1}^{2}Δ(y_{1}) ⋯ Δ(y_{n})  (0)

where Δ = ∑_{1≤i≤n} (\frac{∂f}{∂X_{i}} )^{2}.

Observe that corollary A5 states that for any point y ∈ {f = ϵ_{3}} ⊂ ℝ_{ϵ_{3}}^{n} the gradient grad_{y}(f) = (\frac{∂f}{∂X_{1}} , ⋯, \frac{∂f}{∂X_{n}} ) (y) does not vanish. Notice that the inequality (0) in the definition means that the absolute value of the determinant of the matrix formed by the normalized gradient vectors of f at the points y_{1}, …, y_{n} is greater than ϵ_{1}. Definition 3. A point x ∈ W is called i-quasiangle (0 ≤ i < n) if for each (n − i)-subspace Π ∈ A_{n−i} (see lemma 1) the point x is a 0-quasiangle point in the semi-Pfaffian set W ∩ Π(x) (here we understand 0-quasiangle with respect to a basis in Π whose elements are from ℝ^{n}, in other words have coordinates from ℝ, the role of f plays the restriction of f on Π(x)).

The set of i-quasiangle points of W we denote by Ã_{i}. Observe that Ã_{i} can be determined by a Pfaffian formula and thus is a sub-Pfaffian set (see the definition A4). Definition 4. The points of the set A_{i} = st(Ã_{i}) ⊂ ℝ_{δ}^{n} are called i-angles.

Lemma A7 implies that A_{i} is sub-Pfaffian and definable over ℝ_{1}. Due to lemma A4, A_{i} ⊂ W. Lemma 3. Let P_{i} be an i-facet of P with dimension (see definition A5) dim(W ∩ P_{i}) = i. If for two points x̃ ∈ W ∩ ℝ^{n} ∩ P_{i}, and x ∈ P_{i}^{(δ)} the distance ∥x − x̃∥ is infinitesimal relative to ℝ, then x ∈ Ã_{i}. Remark. Actually, the lemma states that x ∈ A_{i} since x = st(x) ∈ st(Ã_{i}) = A_{i}. Proof of the lemma. Since dim(W ∩ P_{i}) = i, the lemma A1 implies that f vanishes on \overline{P}_{i}. Throughout this paper B_{z}(s) ⊂ ℝ_{ϵ_{3}}^{n} denotes the open ball centered at z with

8 D. GRIGORIEV AND N. VOROBJOV

radius s. There exists 0 < c ∈ ℝ such that u_{j}(x̃) > c, K_{1} + 1 ≤ j ≤ K, therefore there exists 0 < r ∈ ℝ such that u_{j}(y) > \frac{c}{2}, K_{1}+1 ≤ j ≤ K for any y ∈ Bx̃(2r)∩ℝ^{n}, taking into account that the Pfaffian functions u_{j} are defined over ℝ. According to the transfer principle (see the section A2) u_{j}(y) > \frac{c}{2}, K_{1} + 1 ≤ j ≤ K for any y ∈ Bx̃(2r) ∩ ℝ_{ϵ_{3}}^{n}. In particular, u_{j}(x) > \frac{c}{2} > ϵ_{1}, K_{1} + 1 ≤ j ≤ K.

Fix an arbitrary subspace Π ∈ A_{n−i}. Our purpose is to show that x is 0quasiangle in the set W ∩Π(x), which will imply the lemma (see definition 3). Since Π is transversal to P_{i}, the point x is a vertex of the polyhedron P = (P ∩ Π(x))^{(ϵ_{3})} (see lemma 2 and the supposition just after it). The vertex x belongs to at least n − i of (n − i − 1)-facets (of the maximal dimension) of P. Observe that for each of these facets the normalized orthogonal (in Π(x)) vector has the coordinates in ℝ. Choose any T_{1}, …, T_{n−i} among them.

Notice that for any point y ∈ cl(B_{x}(r)) ∩ ℝ_{ϵ_{3}}^{n} (where cl denotes the closure in the topology with a base of all open balls) the inequalities u_{j}(y) > ϵ_{1}, K_{1} + 1 ≤

j ≤ K hold since cl(B_{x}(r)) ⊂ Bx̃(2r). Hence, ∩_{K_{1}+1≦j≦K}{f = 0, & u_{j} ≧ ϵ_{1}}^{(ϵ_{3})}

∩cl(B_{x}(r)) = {f = 0}^{(ϵ_{3})} ∩ cl(B_{x}(r)).

Denote by D ⊂ Π(x) the intersection of the unique closed cone K with the vertex at x formed in Π(x) by (n − i − 1)-planes \overline{T}_{1}, …, \overline{T}_{n−i} containing P, with the ball cl(B_{x}(r)). For any point z ∈ {f = ϵ_{3}} ∩ Π(x) ∩ cl(B_{x}(r)) we have st_{ϵ_{2}}(z) ∈ {f = 0}∩Π(x)∩cl(B_{x}(r)), due to lemma A4. Therefore, st_{ϵ_{2}}(z) ∈ W ∩cl(B_{x}(r))∩Π(x) ⊂ P ∩ cl(B_{x}(r)) ⊂ D, in particular the distance ρ(z, D) from the point z to the set D is infinitesimal relative to ℝ_{ϵ_{2}}. Since the set {f = ϵ_{3}} ∩ Π(x) ∩ cl(B_{x}(r)) is closed in the topology with a base of all open balls, and bounded, the maximum value ρ_{0} of ρ(z, D) over all the points z ∈ {f = ϵ_{3}} ∩ Π(x) ∩ cl(B_{x}(r)) exists (here we use the transfer principle), and is infinitesimal relative to ℝ_{ϵ_{2}}.

Shift (in Π(x)) each of (n − i − 1)-planes \overline{T}_{1}, …, \overline{T}_{n−i} parallel to itself outward from D to the distance ρ_{0}. Denote the resulting shifted (n − i − 1)-planes by \overline{T} ′_{1}, …, \overline{T} ′_{n−i}, respectively. Denote by x′ the (unique) common point of \overline{T} ′_{1} ∩ ⋯ ∩

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 9

\overline{T} ′_{n−i}. Denote by D′ the intersection of the closed cone K′ formed by \overline{T} ′_{1}, …, \overline{T} ′_{n−i}, with the vertex in x′ with the ball cl(B_{x}(r)). Then {f = ϵ_{3}} ∩ Π(x) ∩ cl(B_{x}(r)) ⊂ D′. Observe that the distance ∥x − x′∥ is infinitesimal relative to ℝ_{ϵ_{2}}.

We replace (n−i−1)-planes \overline{T} ′_{j}, 1 ≤ j ≤ n−i (in Π(x)) by some (n−i−1)-planes \overline{T} ′′_{j}, 1 ≤ j ≤ n − i, respectively, in the following way. Take any hyperplane Ω (in Π(x)), defined over ℝ_{δ}, such that the intersection C_{1} = Ω ∩ K ⊂ D. Then C_{1} is a (n − i − 1)-dimensional simplex, let its (n − i − 2)-facets which are the intersections of Ω with T_{1}, …, T_{n−i}, respectively, be determined in Ω by the equations {L_{j} = 0}, 1 ≤ j ≤ n − i for some linear polynomials L_{j} defined over ℝ_{δ}. Thus C_{1} = {L_{1} ≥ 0, …, L_{n−i} ≥ 0}∩Ω. Consider now (n−i−1)-dimensional simplex C_{2} = {L_{1} +ϵ_{2} ≥ 0, …, L_{n−i} +ϵ_{2} ≥ 0}∩Ω ⊃ C_{1}. The facets of C_{2} are {L_{j} = −ϵ_{2}}∩Ω, 1 ≤ j ≤ n−i, and therefore, they are parallel to the corresponding facets of C_{1}. Denote by \overline{T} _{j}^{(3)}, 1 ≤ j ≤ n − i the hyperplane (in Π(x)) containing x and {L_{j} = −ϵ_{2}} ∩ Ω. Denote by K^{(3)} ⊂ Π(x) the cone formed by \overline{T} _{j}^{(3)}, 1 ≤ j ≤ n − i containing C_{2}; observe that K^{(3)} ⊃ K.

We claim that the sine of the angle α between the hyperplanes \overline{T}_{j} and \overline{T} _{j}^{(3)}, (i.e., between vectors, orthogonal to \overline{T}_{j} and \overline{T} _{j}^{(3)} respectively) is infinitesimal relative to ℝ_{δ}. Indeed, consider the unique 2-plane ω_{j}, 1 ≤ j ≤ n − i passing through x and orthogonal to {L_{j} = 0} ∩ Ω. It intersects (n − i − 2)-plane {L_{j} = 0} ∩ Ω (respectively, (n − i − 2)-plane {L_{j} = −ϵ_{2}} ∩ Ω) at the unique point y_{j} (respectively y_{j}^{(3)}). Observe that the vector in ω_{j} orthogonal to the line ℓ_{j} passing through x and y_{j} (respectively, the line ℓ_{j}^{(3)} passing through x and y_{j}^{(3)}) is orthogonal to \overline{T}_{j} (respectively, \overline{T} _{j}^{(3)}). The segment (y_{j}, y_{j}^{(3)}) lies on the line ω_{j} ∩ Ω and is orthogonal to {L_{j} = 0} ∩ Ω. Hence the distance between (n − i − 2)-planes {L_{j} = 0} ∩ Ω and {L_{j} = −ϵ_{2}}∩Ω, which is equal to the length of the segment [y_{j}, y_{j}^{(3)}], is infinitesimal relative to ℝ_{δ}. Since the angle α equals to the angle between the lines ℓ_{j} and ℓ_{j}^{(3)}, we conclude that sin α is infinitesimal relative to ℝ_{δ} taking into account that in the

10 D. GRIGORIEV AND N. VOROBJOV

triangle (x, y_{j}, y_{j}^{(3)}) the vertices x and y_{j} are defined over ℝ_{δ}, therefore the sides (x, y_{j}) and (x, y_{j}^{(3)}) are not infinitesimal relative to ℝ_{δ} and (y_{j}, y_{j}^{(3)}) is infinitesimal relative to ℝ_{δ}. This proves the claim.

Let us show that there exists an element 0 < β ∈ ℝ_{ϵ_{2}} such that for any two points z_{1} ∈ ∂C_{1}, z_{2} ∈ ∂ C_{2} from the boundaries, (see definition A8 (here we mean the boundary in the hyperplane Ω)), the sine of the angle between the lines (x, z_{1}) and (x, z_{2}) is greater or equal to β. Since both points z_{1}, z_{2} range over bounded closed sets, there exists (due to the transfer principle) the minimum β of these sines. Observe that β > 0 since ∂C_{1} ∩ ∂C_{2} = ∅. One could define the element β by a formula of the language L_{ϵ_{2}}. Therefore, β ∈ ℝ_{ϵ_{2}} by the transfer principle, as was to be shown.

Note that the cones K and K′ are isometric. We define the desired (n − i − 1)- planes \overline{T} ′′_{j}, 1 ≤ j ≤ n−i as the images of \overline{T} _{j}^{(3)}, respectively, under the shift mapping the cone K onto K′, then the cone K′′ formed by \overline{T} ′′_{j}, 1 ≤ j ≤ n − i, is the image of the cone K^{(3)}.

For every 1 ≤ j ≤ n − i, pick a point x_{j} ∈ {f = ϵ_{3}} ∩ Π(x) ∩ cl B_{x}(r) with the property that x_{j} is the nearest to \overline{T} ′′_{j} on the (bounded and closed) set \{f = ϵ_{3}} ∩ Π(x) ∩ cl B_{x}(r). Lemma A4 entails that there exists a point y ∈ {f = ϵ_{3}} ∩ Π(x) ∩ B_{x}(r) such that ∥x − y∥ is infinitesimal relative to ℝ_{ϵ_{2}}, therefore ∥x′ − y∥ is infinitesimal relative to ℝ_{ϵ_{2}} as well, hence the distance from x_{j} to \overline{T} ′′_{j} is also infinitesimal relative to ℝ_{ϵ_{2}}. Denote by x′′_{j} ∈ \overline{T} ′′_{j} the orthogonal projection of x_{j} on \overline{T} ′′_{j}. Let us prove that ∥x_{j} − x′∥ is infinitesimal relative to ℝ_{ϵ_{2}}. Since x_{j} ∈ ({f = ϵ_{3}} ∩ Π(x) ∩ cl(B_{x}(r))) ⊂ D′, the segment (x_{j}, x′′_{j}) intersects ∂K′ (here we mean the boundary in Π(x)) at the unique point x′_{j}. Since the sine of the angle γ between the lines (x′, x_{j}) and (x′, x′′_{j}) is greater than or equal to the sine of the angle between the lines (x′, x′′_{j}) and (x′, x′_{j}) which, in its turn, is greater or equal to β (see above), we conclude that sin γ ≥ β ∈ ℝ_{ϵ_{2}}. Therefore, ∥x′ − x_{j}∥ = \frac{∥x_{j}−x′′_{j}∥}{sin γ} is infinitesimal relative to ℝ_{ϵ_{2}}, 1 ≤ j ≤ n−i, which was to be proved. Hence, ∥x−x_{j}∥

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 11

is infinitesimal relative to ℝ_{ϵ_{2}} as well, in particular x_{j} ∈ B_{x}(r).

Observe that the gradient grad_{x_{j}}(f̂) (where f̂ denotes the restriction of f on Π(x), cf. Definition 3) does not vanish because x_{j} ∈ {f = ϵ_{3}} ∩ Π(x) (see corollary A5) and it is orthogonal to the hyperplane \overline{T} ′′_{j} (in Π(x)), as x is the nearest to \overline{T} ′′_{j} on the set {f = ϵ_{3}} ∩ Π(x) ∩ cl B_{x}(r). Since the sines of the angles between any pair of hyperplanes \overline{T}_{j_{1}}, \overline{T}_{j_{2}} (in Π(x)) is greater than a certain c, 0 < c ∈ ℝ, we conclude that the sines of the angles between any pair of hyperplanes \overline{T} ′′_{j_{1}}, \overline{T} ′′_{j_{2}} is greater than c/2 according to the claim proved above (stating that the sine of the angle between \overline{T}_{j_{1}} and \overline{T} ′′_{j_{1}} is infinitesimal relative to ℝ_{δ}). Therefore

det (\frac{grad_{x_{1}}(f̂)}{∥grad_{x_{1}}(f̂)∥}, …, \frac{grad_{x_{n−i}}(f̂)}{∥grad_{x_{n−i}}(f̂)∥}) > c_{1} > 0

for a suitable c_{1} ∈ ℝ.

Taking the points x_{1}, …, x_{n−i} as the points y_{1}, …, y_{n−i} in the definition 2 we get that x is 0-quasiangle in the semi-Pfaffian set W ∩Π(x), whence x is i-quasiangle because (n − i)-plane Π ∈ A_{n−i} was chosen arbitrarily. □ Corollary. Let a point x̃ ∈ W ∩P_{i}∩ℝ^{n} and the dimension in the point x̃ dimx̃(W ∩ P_{i}) = i, then

(a) dimx̃(A_{i} ∩ P_{i}^{(δ)}) = i;

(b) dim(A_{i} ∩ P_{i}^{(ϵ_{3})}) = i.

Proof. Lemma 3 and the remark following this lemma imply that for any 0 < ρ ∈ ℝ_{δ} which is infinitesimal relative to ℝ, we have the inclusion (Bx̃(ρ) ∩ P_{i}^{(δ)}) ⊂ A_{i}, this provides a).

Moreover, lemma 3 and the remark imply that (Bx̃(ρ) ∩ P_{i}^{(δ)}) ⊂ st(Ã_{i} ∩ P_{i}^{(ϵ_{3})}). Thus, b) follows from lemma A8. □ Lemma 4. dim(A_{i}) ≤ i Proof. First let us reduce the proof to the case i = 0, in which Ã_{0}, A_{0} are defined for a set W given by Pfaffian functions u_{1}, …, u_{K} defined over ℝ_{δ} (rather than ℝ), see section A2.

12 D. GRIGORIEV AND N. VOROBJOV

Thus, let i ≥ 1 and suppose that e = dim(A_{i}) ≥ i + 1. Due to corollary A1, there exists a nonsingular point y ∈ A_{i} such that dim_{y}(A_{i}) = e. Denote by T_{y} the tangent plane to A_{i} at the point y. Since dim(T_{y}) = e one can find (n − i)- subspace Π ∈ A_{n−i} such that dim(T_{y} ∩ Π(y)) = e − i. Take any (n − e)-subspace R ⊂ Π defined over ℝ_{δ} for which (T_{y} ∩ R(y)) = {y}. Consider the linear orthogonal projection π : ℝ_{ϵ_{3}}^{n} → ℝ_{ϵ_{3}}^{e} onto e-subspace along R. Then dim π(T_{y}) = e. Therefore, π(A_{i}) ⊂ ℝ_{δ}^{e} contains e-dimensional ball B_{π(y)}(r) for a certain 0 < r ∈ ℝ_{δ} (by the implicit function theorem and the transfer principle).

For any point x ∈ A_{i} there is a point x′ ∈ Ã_{i} such that st(x′) = x, hence st(π(Ã_{i})) ⊃ B_{π(y)}(r).

By assumption that the lemma is valid for the case i = 0.

Then for any point z ∈ ℝ_{δ}^{n} applying this assumption to the set of 0-angle points of the intersection Π(z) ∩ W we conclude that the sub-Pfaffian set st(Π(z) ∩ Ã_{i}) has the dimension at most 0 (taking into account the definition 3 of i-quasiangle points and that Π(z) is defined over ℝ_{δ}).

Let us show that π(Ã_{i}) does not contain a ball B_{w}(r_{1}) for any 0 < r_{1} ∈ ℝ_{δ} and w ∈ ℝ_{ϵ_{3}}^{e}. Assume the contrary, then there exists a point w_{1} ∈ B_{w}(r_{1}) ∩ ℝ_{δ}^{e}. Let z_{1} ∈ ℝ_{δ}^{n} be a point such that π(z_{1}) = w_{1}. Denote Π_{1} = π(Π), then dim Π_{1} = e − i, Π = π^{−1}(Π_{1}). Then the following inequalities hold:

dim st(Π_{1}(w_{1}) ∩ π(Ã_{i})) ≥ dim st(Π_{1}(w_{1}) ∩ B_{w}(r_{1})) = e − i ≥ 1.

On the other hand, Π_{1}(w_{1}) ∩ π(Ã_{i}) = π(Ã_{i} ∩ Π(z_{1})), and, therefore,

dim st(Π_{1}(w_{1}) ∩ π(Ã_{i})) ≤ dim st(Ã_{i} ∩ Π(z_{1})) ≤ 0,

(the latter inequality was proved above). The obtained contradiction shows that π(Ã_{i}) does not contain a ball B_{w}(r_{1}) for any 0 < r_{1} ∈ ℝ_{δ}.

We claim that for any ball B_{z_{2}}(r_{2}) ⊂ B_{π(y)}(r) defined over ℝ_{ϵ_{3}} such that 0 < r_{2} ∈ ℝ_{δ}, the intersection B_{z_{2}}(r_{2}) ∩ ∂π(Ã_{i}) ≠ ∅. Assume the contrary. Then

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 13

either B_{z_{2}}(r_{2}) ⊂ π(Ã_{i}) or B_{z_{2}}(r_{2}) ∩ π(Ã_{i}) = ∅. The inclusion B_{z_{2}}(r_{2}) ⊂ π(Ã_{i}) is impossible as was shown above. If B_{z_{2}}(r_{2}) ∩ π(Ã_{i}) = ∅, then st(z_{2}) ∉ st(π(Ã_{i})), the latter contradicts to the inclusions st(π(Ã_{i})) ⊃ B_{π(y)}(r) ⊃ B_{st(z_{2})}(r_{2}/2) of the sets in the space ℝ_{δ}^{e}. This proves the claim.

Because of lemma A3, dim(∂(π(Ã_{i}))) ≤ e − 1. Applying lemma A8, we get dim(st(∂(π(Ã_{i})))) ≤ e − 1.

On the other hand we shall now prove that st(∂(π(Ã_{i}))) ⊃ B_{π(y)}(r). This contradiction completes the proof of the reduction of the lemma to the case i = 0. Indeed, let z_{3} ∈ B_{π(y)}(r). Observe that the set D = {∥z − z_{3}∥^{2} : z ∈ ∂(π(Ã_{i}))} is sub-Pfaffian. Due to Corollary A4, D is a finite union of points and intervals. Let ω be the minimal among these points and the endpoints of these intervals. Suppose that z_{3} ∉ st(∂(π(Ã_{i}))), i.e. there does not exist z ∈ ∂(π(Ã_{i})) such that st(z) = z_{3}. Thus, ω > r_{3}^{2} for an element 0 < r_{3} ∈ ℝ_{δ}. It follows that B_{z_{3}}(r_{3}) ∩ ∂(π(Ã_{i})) = ∅. This contradicts the claim just proved.

Now let i = 0. Suppose the statement of the lemma is wrong and dim(A_{0}) = s ≥ 1. There is a linear projection π : ℝ_{δ}^{n} → ℝ_{δ}^{s} onto a certain coordinate s-subspace, such that π(A_{0}) ⊃ B_{z}(r) for some z ∈ ℝ_{δ}^{s}, 0 < r ∈ ℝ_{δ}. Choose an open interval L ⊂ B_{z}(r) of the length 2r passing through z.

Our nearest purpose is to prove the existence of a sub-Pfaffian curve (i.e. onedimensional sub-Pfaffian set) C_{0} ⊂ A_{0} such that π(C_{0}) = L and the mapping π : C_{0} → L is bijective. This follows from the next, a more general construction.

Let V ⊂ F^{n}, U ⊂ F^{m} be sub-Pfaffian sets where F is one of the fields ℝ_{j} defined in the section A2 and φ : V → U be a sub-Pfaffian mapping (i.e. a mapping with a sub-Pfaffian graph). Let us describe one of the possible ways to construct a sub-Pfaffian set V_{0} ⊂ V such that the restriction φ : V_{0} → φ(V) of φ is bijective.

For every point u ∈ φ(V) take the (unique) point v_{u} ∈ V such that φ(v_{u}) = u according to the following rule (actually, this rule is quite flexible).

A projection π_{1}(φ^{−1}(u)) of φ^{−1}(u) onto the axis X_{1} is a union of a finite number

14 D. GRIGORIEV AND N. VOROBJOV

of intervals (with or without endpoints) since π_{1}(φ^{−1}(u)) is sub-Pfaffian (see Corollary A4). Let 𝔞_{1}, 𝔞_{2} be the endpoints of the leftmost among these intervals (note that a sub-Pfaffian set is always bounded, see Definition A4). Then \frac{𝔞_{1}+𝔞_{2}}{2} ∈ π_{1}(φ^{−1}(u)). Consider the projection π_{2}(φ^{−1}(u) ∩ \{X_{1} = \frac{𝔞_{1}+𝔞_{2}}{2}\}) onto the axis X_{2}. Continuing in the similar way, after n steps we obtain a point v_{u} = (\frac{𝔞_{1}+𝔞_{2}}{2}, …) ∈ φ^{−1}(u). We define V_{0} as a set of all the obtained points v_{u} for all u ∈ φ(V). One can easily prove that V_{0} is sub-Pfaffian and the mapping φ : V_{0} → φ(V) is bijective.

Applying this construction to the mapping π|_{π^{−1}(L)∩A_{0}} : π^{−1}(L) ∩ A_{0} → L we get a required sub-Pfaffian curve C_{0} ⊂ A_{0}. Since there is only a finite number of connected components of C_{0} (see Corollary A3), there exists a connected component C such that π(C) is an interval of a length r_{0} > 0 for a certain r_{0} ∈ ℝ_{δ}. Then the completion C^{(ϵ_{3})} ⊂ ℝ_{ϵ_{3}}^{n} is a connected component of the curve C_{0}^{(ϵ_{3})} ⊂ ℝ_{ϵ_{3}}^{n} (see the section A3).

Fix a nonsingular point x ∈ C (due to corollaries A1, A4 C has only a finite number of singular points). Denote by τ ⊂ ℝ_{δ}^{n} the tangent line to C at x, then its completion τ^{(ϵ_{3})} ⊂ ℝ_{ϵ_{3}}^{n} is tangent to C^{(ϵ_{3})}. After a suitable linear coordinate transformation (defined over ℝ_{δ}) one can assume that x = 0 and τ coincides with the axis X_{n}. Denote by γ the projection mapping on the axis X_{n}.

There exists 0 < μ ∈ ℝ_{δ} satisfying the following properties:

(i) the unique connected component c of the intersection C∩{−μ < X_{n} < μ} ⊂ ℝ_{δ}^{n}, containing 0, is a nonsingular curve and the mapping γ^{−1} : (−μ, μ) → c is definable and doubly differentiable;

(ii) there exists 0 < λ ∈ ℝ_{δ} such that for any y ∈ (−μ, μ) the inequality

∥γ^{−1}(0, …, 0, y) − (0, …, 0, y)∥ ≤ λ|y|^{2} holds. One can prove the existence of μ for the curves in ℝ^{n} using Taylor formula, and

then for C applying the transfer principle.

The transfer principle also implies that (i), (ii) hold for the completions c^{(ϵ_{3})} ⊂ C^{(ϵ_{3})} and any y ∈ (−μ, μ)^{(ϵ_{3})}.

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 15

The angle between a line ℓ and a hyperplane P in ℝ_{ϵ_{3}}^{n} is defined as a difference between π/2 and the angle between ℓ and the vector orthogonal to P. Observe that there exists 0 < ν ∈ ℝ_{ϵ_{1}} such that if n normalized vectors v_{1}, … v_{n} ∈ ℝ_{ϵ_{3}}^{n} satisfy the inequality |det(v_{1}, … v_{n})| > ϵ_{1}, then for any hyperplane P there is i, 1 ≤ i ≤ n for which the sine of the angle between v_{i} and P is greater than ν (actually, one could take ν = ϵ_{1}/2 but we will not use this particular value).

Introduce the sub-Pfaffian set V ⊂ ℝ_{ϵ_{3}}^{n} consisting of all the points z = (z_{1}, …, z_{n}) ∈ ℝ_{ϵ_{3}}^{n} such that

(1) z ∈ {f = ϵ_{3}}, |z_{n}| < μ;

(2) sine of the angle between grad_{z}(f − ϵ_{3}) and the hyperplane {X_{n} = 0} is greater than ν;

(3) for a given z_{n} the minimum of the distance to the axis X_{n} (i.e., of the function (X_{1}^{2} + ⋯ + X_{n−1}^{2})^{1/2}) on the set of all the points satisfying 1), 2) is attained at z.

Let us apply the above construction to the projection γ : V → (−μ, μ). The construction supplies us with a sub-Pfaffian subset V_{0} ⊂ V such that each nonempty preimage γ^{−1}(y) contains exactly one point from V_{0}. Therefore dim(V_{0}) ≤ 1.

We claim that, actually, dim(V_{0}) = 1. Suppose the contrary, then V_{0} would consist of a finite number of points (see corollary A4). We show, however, that V_{0} contains infinitely many points.

Indeed, take an arbitrary point y ∈ ℝ_{δ} ∩ (−μ, μ) and the (unique) point w ∈ c such that γ(w) = (0, …, 0, y). Since c ⊂ A_{0} there exists (see the definition 4 of 0-angle points) a point w_{1} ∈ Ã_{0} such that st(w_{1}) = w, therefore (see definition 2 of 0-quasiangle points) there exists a point w_{2} ∈ {f = ϵ_{3}} for which ∥w_{1}−w_{2}∥ ≤ ϵ_{2} and the sine of the angle between the vector grad_{w_{2}}(f−ϵ_{3}) and the hyperplane {X_{n} = 0} is greater than ν (see (0)). Because st∥w_{2}−w∥ = 0 and for the orthogonal projection ∥γ(w_{2}) − γ(w)∥ ≤ ∥w_{2} − w∥, we deduce that st(γ(w_{2})) = st(γ(w)) = γ(w). Since the point w_{2} satisfies the conditions 1), 2) in the definition of V, there exists a

16 D. GRIGORIEV AND N. VOROBJOV

point w_{3} ∈ {f = ϵ_{3}} such that γ(w_{3}) = γ(w_{2}), the sine of the angle between grad_{w_{3}}(f − ϵ_{3}) and the hyperplane {X_{n} = 0} is greater than ν, and w_{3} has the minimal distance to the axis X_{n} among the points with these properties. Then w_{3} ∈ V.

Thus, we have shown that for each point y ∈ ℝ_{δ} ∩ (−μ, μ) there exists a point w_{3} ∈ V such that st(γ(w_{3})) = (0, …, 0, y). Because of the above construction, there exists the unique point w_{4} ∈ V_{0} for which γ(w_{4}) = γ(w_{3}). Hence V_{0} contains an infinite number of points, i.e. dim(V_{0}) = 1.

Let V_{0} = ∪_{i}V_{i} be the decomposition of V_{0} into the connected components. Since V_{0} is sub-Pfaffian, it has only a finite number of singular points and a finite number of points at which the tangent to the curve V_{0} is orthogonal to the axis X_{n} (i.e. of the critical points of the mapping γ), here we invoke corollaries A1, A4. It follows that each V_{i} admits a finite partition V_{i} = ∪_{j}V_{ij} ∪ ∪_{j_{1}}v_{ij_{1}}, where every V_{ij} is a nonsingular connected sub-Pfaffian curve (without the endpoints) not containing the critical points of γ, and every v_{ij_{1}} is a set consisting of a single point.

We have shown above that st(γ(V_{0})) = [−μ, μ]. Since γ(V_{ij}) ⊂ (−μ, μ)^{(ϵ_{3})} is connected (as an image of a connected curve), it is an interval, hence st(γ(V_{ij})) ⊂ [−μ, μ] is a closed interval. Therefore, there are i_{0}, j_{0} for which an interval I = st(γ(V_{i_{0}j_{0}})) has a positive length |I| ∈ ℝ_{δ}, besides I contains 0 and does not lie entirely to the left of 0.

Due to the implicit function theorem, one may represent the curve V_{i_{0}j_{0}} in a parametrical form: (X_{1}(X_{n}), …, X_{n−1}(X_{n}), X_{n}) where X_{1}, …, X_{n−1} are smooth functions. Observe that for any point z = (X_{1}(z_{n}), …, X_{n−1}(z_{n}), z_{n}) ∈ V_{i_{0}j_{0}} the tangent vector (Ẋ_{1}(z_{n}), …, Ẋ_{n−1}(z_{n}), 1) at this point to the curve V_{i_{0}j_{0}} has a sine of the angle with the axis X_{n} greater than ν, since this tangent vector is orthogonal to grad_{z}(f −ϵ_{3}), taking into account inclusions V_{0} ⊂ V ⊂ {f = ϵ_{3}}. In other words

∑_{1≤i≤n−1}(Ẋ_{i}(z_{n}))^{2} > ν^{2}/(1 − ν^{2}).

For each pair of indices 1 ≤ i < j ≤ n−1 either there are at most a finite number

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 17

of the tangent vectors (Ẋ_{1}(z_{n}), …, Ẋ_{n−1}(z_{n}), 1) at the points of the curve V_{i_{0}j_{0}} such that Ẋ_{i}(z_{n}) = ±Ẋ_{j}(z_{n}) or all these vectors satisfy one of the two conditions: Ẋ_{i}(z_{n}) = Ẋ_{j}(z_{n}) or Ẋ_{i}(z_{n}) = −Ẋ_{j}(z_{n}), because V_{i_{0}j_{0}} is sub-Pfaffian. Therefore, there exists a connected sub-Pfaffian curve V ⊂ V_{i_{0}j_{0}} for which the length of the interval st(γ(V)) ∈ ℝ_{δ} is positive, besides st(γ(V)) contains 0 and does not lie entirely to the left of 0. Apart from that, either |Ẋ_{i}(z_{n})| ≠ |Ẋ_{j}(z_{n})|, for any pair 1 ≤ i < j ≤ n−1 and any point (X_{1}(z_{n}), …, X_{n−1}(z_{n}), z_{n}) ∈ V, or for a certain pair 1 ≤ i < j ≤ n−1, one of the two conditions Ẋ_{i}(z_{n}) = Ẋ_{j}(z_{n}) or Ẋ_{i}(z_{n}) = −Ẋ_{j}(z_{n}) holds for any point from V. Let us assume that |Ẋ_{i}(z_{n})| ≠ |Ẋ_{j}(z_{n})| for any pair 1 ≤ i < j ≤ n − 1 (the case |Ẋ_{i}(z_{n})| = |Ẋ_{j}(z_{n})| can be treated in a similar way). There exists s, 1 ≤ s ≤ n − 1 such that |Ẋ_{s}(z_{n})| > |Ẋ_{j}(z_{n})|, 1 ≤ j ≤ n − 1, s ≠ j for all the points for V. Moreover, Ẋ_{s}(z_{n}) has a constant nonnegative sign for all the points from V. For definiteness suppose that Ẋ_{s}(z_{n}) > 0 for all the points from V (the case Ẋ_{s}(z_{n}) < 0 can be considered in a similar manner). Then Ẋ_{s}(z_{n}) > ν/((n − 1)(1 − ν^{2}))^{1/2} = ν_{0} ∈ ℝ_{ϵ_{1}} and ν_{0} > 0.

Let an interval [0, μ_{2}] ⊂ st(γ(V)) ⊂ [−μ, μ] where 0 < μ_{2} ∈ ℝ_{δ}. Then for any μ_{3}, μ_{4} ∈ ℝ_{δ}, such that 0 < μ_{3} < μ_{4} < μ_{2}, the completion of the interval [μ_{3}, μ_{4}]^{(ϵ_{3})} ⊂ γ(V). Since Ẋ_{s}(z_{n}) > ν_{0} for any z_{n} ∈ [μ_{3}, μ_{4}]^{(ϵ_{3})}, for any point η ∈ [μ_{3}, μ_{4}]^{(ϵ_{3})} the inequality

X_{s}(η) − X_{s}(μ_{3}) ≥ ν_{0}(η − μ_{3})

holds. Indeed, the latter statement could be written as a formula of the first-order theory of real closed fields, in the case of the field ℝ it is true because

X_{s}(ν) − X_{s}(μ_{3}) = ∫_{μ_{3}}^{ν} Ẋ_{s} ≥ ν_{0}(ν − μ_{3}),

then use the transfer principle.

Let y ∈ (−μ, μ) ∩ ℝ_{δ}. We have proved above that for the unique point w = γ^{−1}(0, …, 0, y) ∈ c ⊂ A_{0} there exists a point w_{1} ∈ Ã_{0} such that st(w_{1}) = w, besides there exists a point w_{2} ∈ {f = ϵ_{3}} such that ∥w_{1} − w_{2}∥ ≤ ϵ_{2} and the

18 D. GRIGORIEV AND N. VOROBJOV

sine of the angle between the vector grad_{w_{2}}(f − ϵ_{3}) and the hyperplane {X_{n} = 0} is greater than ν. Then the distance from w_{2} to the axis X_{n} does not exceed ∥w_{2} − w_{1}∥ + ∥w_{1} − w∥ + ∥w − (0, …, 0, y)∥ ≤ ϵ_{2} + ∥w_{1} − w∥ + λy^{2} ≤ λ_{0}y^{2} for λ ∈ ℝ_{δ}, introduced in (ii) above, and any λ < λ_{0} ∈ ℝ_{δ}. So the distance to the axis X_{n} from the unique point w_{4} ∈ V_{0}, for which γ(w_{4}) = γ(w_{2}), also does not exceed λ_{0}y^{2}. Note that st(γ(w_{4})) = (0, …, 0, y).

On the other hand if y ∈ [μ_{3}, μ_{4}] ∩ ℝ_{δ}, then applying the above arguing to the point (y + μ_{3})/2 instead of y we prove the existence of a point w_{5} ∈ V_{0} such that st(γ(w_{5})) = (0, …, 0, (y + μ_{3})/2) and the distance to the axis X_{n} from the point w_{5} does not exceed λ_{0}((y + μ_{3})/2)^{2}. Arguing as above, we get

X_{s}(w_{4}) − X_{s}(w_{5}) ≥ ν_{0}∥γ(w_{4}) − γ(w_{5})∥ > ν_{1}(y − μ_{3})/2

for arbitrary ν_{1} ∈ ℝ_{ϵ_{1}}, 0 < ν_{1} < ν_{0}. Then either the distance from the point w_{4} to the axis X_{n} or the distance from the point w_{5} to X_{n} is greater than ν_{1}(y−μ_{3})/4, on the other hand both distances do not exceed λ_{0}y^{2}. Taking any y, 0 < y ∈ ℝ_{δ}, such that y < ν_{1}/(ν_{1} + 4λ_{0}) and μ_{3} = y^{2}, we get a contradiction because ν_{1}(y − y^{2})/4 > λ_{0}y^{2}. □ III. Flat Points. Definition 4. Let 0 ≤ i ≤ n − 1. A point x ∈ A_{i} is i-flat if there exists an i-plane Π, passing through x such that dim(Π ∩ A_{i}) = i.

Denote by ϕ_{i} ⊂ A_{i} the set of i-flat points. Note that for i = 0 lemma 4 implies that dim A_{0} ≤ 0, i.e. A_{0} consists of at most finite set of points (see corollary A4), therefore ϕ_{0} = A_{0}. Lemma 5. a) There is at most a finite number of i-planes Π such that dim(Π ∩ ϕ_{i}) = i;

b) ϕ_{i} is contained in the union of all i-planes described in a). Proof. If ϕ_{i} = ∅, the lemma is trivial, so suppose that ϕ_{i} ≠ ∅. Since ϕ_{0} = A_{0}

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 19

consists of a finite number of points, the lemma for the case i = 0 is obvious. So, in what follows we assume that i ≥ 1.

b) is evident. Note that if Π satisfies a) then dim(Π ∩ A_{i}) = i since ϕ_{i} ⊂ A_{i}. Introduce a set ϕ̂_{i} ⊂ ϕ_{i} consisting of all the points y ∈ ϕ_{i} for which there

exists an i-plane Π passing through y, such that for suitable 0 < r ∈ ℝ_{δ} we have B_{y}(r) ∩ Π ⊂ ϕ_{i}. The set ϕ̂_{i} is obviously sub-Pfaffian.

Besides, dim ϕ̂_{i} = i. Indeed, lemma 4 implies that dim ϕ̂_{i} ≤ i. On the other hand as ϕ_{i} ≠ ∅, there exists i-plane Π such that dim(Π ∩ A_{i}) = i, hence Π ∩ A_{i} ⊃ Π ∩ B_{y_{1}}(r_{1}) for some y_{1} ∈ Π, 0 < r_{1} ∈ ℝ_{δ}. Then Π ∩ B_{y_{1}}(r_{1}) ⊂ ϕ̂_{i}, i.e. dim ϕ̂_{i} ≥ i.

If suffices to prove that there exists only a finite number of i-planes Π for which dim(Π ∩ ϕ̂_{i}) = i. This would imply the item a) of the lemma since for any i-plane Π such that dim(Π ∩ ϕ_{i}) = i we have dim(Π ∩ ϕ̂_{i}) = i.

Denote by ˆ ϕ̂_{i} ⊂ ϕ̂_{i} the set of all nonsingular points of ϕ̂_{i}. The set ϕ̂_{i} ∖ ˆ ϕ̂_{i} of all singular points is sub-Pfaffian and dim(ϕ̂_{i} ∖ ˆ ϕ̂_{i}) ≤ i − 1 (see corollary A1 and lemma A2). For any point y_{2} ∈ ˆ ϕ̂_{i} there is the unique i-plane Π′ such that for an appropriate 0 < r_{2} ∈ ℝ_{δ} we have B_{y_{2}}(r_{2}) ∩ Π′ ⊂ ϕ̂_{i}. Then for a suitable 0 < r_{3} ∈ ℝ_{δ}, a certain neighbourhood of y_{2} in ϕ̂_{i} coincides with B_{y_{2}}(r_{3}) ∩ Π′, moreover B_{y_{2}}(r_{3}) ∩ Π′ is a neighbourhood of y_{2} in ˆ ϕ̂_{i}.

If dim(Π ∩ ϕ̂_{i}) = i for i-plane Π then Π ∩ ϕ̂_{i} contains a nonsingular point y_{3} ∈ ˆ ϕ̂_{i} (since dim(ϕ̂_{i} ∖ ˆ ϕ̂_{i}) ≤ i − 1); moreover a neighbourhood of y_{3} in ˆ ϕ̂ coincides with B_{y_{3}}(r_{4}) ∩ Π for a suitable 0 < r_{4} ∈ ℝ_{δ}. Thus, it is sufficient to show that there is only a finite number of i-planes Π such that dim(Π ∩ ˆ ϕ̂_{i}) = i.

Each connected component of ˆ ϕ̂_{i} is contained in an i-plane Π, since for any point y_{4} ∈ ˆ ϕ̂_{i} its certain neighbourhood in ˆ ϕ̂_{i} coincides with B_{y_{4}}(r_{5}) ∩ Π′′ for some 0 < r_{5} ∈ ℝ_{δ} and i-plane Π′′. Because the number of connected components of ˆ ϕ̂_{i} is finite (see corollary A3), the number of i-planes Π such that dim(Π ∩ ˆ ϕ̂_{i}) = i is also finite. □

Lemma 6. If a connected component φ of ϕ_{i} has a nonempty intersection φ∩P_{i} ≠ ∅ with a i-facet P_{i} of P, then φ ⊂ P_{i}.

Proof. First we prove for a connected component φ_{0} of ϕ_{i} the following statement: if φ_{0} ∩ cl(P_{i}) ≠ ∅ then φ_{0} ⊂ cl(P_{i}). Assume the contrary. Then there exists a point y ∈ φ_{0} ∩ \overline{P}_{i} such that y ∈ cl(φ_{0} ∖ \overline{P}_{i}) ⊂ cl(Φ_{i} ∖ \overline{P}_{i}). Due to lemma 5, there is a finite family P of i-planes Π such that dim(Π ∩ ϕ_{i}) = i and ϕ_{i} lies in the union of all these i-planes. Let us show that there exists Π′ ∈ P, Π′ ≠ \overline{P}_{i} such that y ∈ Π′. Indeed, let y_{j} ⟶_{j→∞} y, where y_{j} ∈ φ_{0} ∖ \overline{P}_{i}. For each j there is Π′′ ∈ P such that y_{j} ∈ Π′′ (obviously Π′′ ≠ \overline{P}_{i}). Since P is finite there exists an infinite subsequence y_{j_{ℓ}}, 1 ≤ ℓ < ∞ and Π′′′ ∈ P for which y_{j_{ℓ}} ∈ Π′′′, 1 ≤ ℓ < ∞. Thus y ∈ Π′′′ ≠ \overline{P}_{i}.

Since ϕ_{i} ⊂ A_{i} ⊂ W ∩ ℝ_{δ}^{n} (see the remark following the definition 4) the function f vanishes on the intersection of Π′′′ with the domain of f (see the lemma A1), taking into account that dim(Π′′′ ∩ ϕ_{i}) = i. Besides u_{K_{1}+1}(y) > 0, …, u_{K}(y) > 0, therefore u_{K_{1}+1}, …, u_{K} are positive also in B_{y}(ρ) for an appropriate 0 < ρ ∈ ℝ_{δ}. Hence Π′′′ ∩ B_{y}(ρ) ⊂ W ∩ ℝ_{δ}^{n}. This contradicts to the inclusion W ∩ ℝ_{δ}^{n} ⊂ P^{(δ)} because y belongs to the closure cl(P_{i}) of i-facet of the convex polyhedron P^{(δ)}. Thus φ_{0} ⊂ cl(P_{i}), and the statement is proved.

To complete the proof of the lemma it suffices to show that φ∩(cl(P_{i})∖P_{i}) = ∅. If z ∈ φ ∩ (cl(P_{i}) ∖ P_{i}) then there is another i-facet P′_{i} of P such that z ∈ cl(P′_{i}). Then, by the proved above, φ ⊂ cl(P′_{i}), this contradicts to φ ∩ P_{i} ≠ ∅. □

Our next purpose is to explicitly describe (see lemma 7 below) the sufficient condition for i-flatness of a point x ∈ A_{i} by means of Pfaffian formula with purely existential quantifier prefix.

Let Π be an i-plane containing x and for some points v_{1}, …, v_{i} ∈ Π ∩ A_{i}, the vectors v_{1} − x, …, v_{i} − x be linearly independent. Denote by γ_{1}, …, γ_{(i+1)n} the coordinates of the vectors x, v_{1}, …, v_{i}. Due to lemma A9, 1) the degree of sub-Pfaffian transcendency [γ_{1}, …, γ_{(i+1)n}]_{ℝ_{1}} ≤ (i + 1)n ≤ n^{2}. Introduce the points

w^{(j)} = x + ∑_{1≤ℓ≤i}δ_{ℓ}^{(j)}(v_{ℓ} − x) ∈ Π, 1 ≤ j ≤ n^{2} + 1.

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 21

Lemma 7. Let the points x, v_{1}, …, v_{i} ∈ A_{i} ∩ Π. If w^{(1)}, …, w^{(n^{2}+1)} ∈ A_{i} ∩ Π, then x is i-flat and moreover dim(A_{i} ∩ Π) = i. Proof. Suppose that on the contrary, dim(A_{i}∩Π) ≤ i−1. Consider the sub-Pfaffian set A ⊂ ℝ_{δ}^{(i+1)n+i} consisting of all the points

(y_{1}, …, y_{n}, y_{1,1}, …, y_{1,n}, y_{2,1}, …, y_{2,n}, …, y_{i,1}, …, y_{i,n}, z_{1}, …, z_{i})

for which (y_{1}, …, y_{n}) + ∑_{1≤ℓ≤i}z_{ℓ}((y_{ℓ,1}, …, y_{ℓ,n}) − (y_{1}, …, y_{n})) ∈ A_{i} (cf. expressions

for w^{(j)}). Then A is definable over ℝ_{1} since A_{i} is definable over ℝ_{1} (see the remark following the definition 4). Besides dim(A∩{(y_{1}, …, y_{n}, y_{1,1}, …, y_{1,n}, …, y_{i,1}, …, y_{i,n}) = (γ_{1}, …, γ_{(i+1)n})}) = dim(A_{i} ∩ Π) ≤ i − 1 by the supposition. According to the definition A10, this means that [(δ_{1}^{(j)}, …, δ_{i}^{(j)}) : (γ_{1}, …, γ_{(i+1)n})]_{ℝ_{1}} ≤ i − 1, for each 1 ≤ j ≤ n^{2} + 1 since w^{(j)} ∈ A_{i} ∩ Π. Applying several times lemma A10 proceeding by induction on j, and taking into account that [(δ_{1}^{(j)}, …, δ_{i}^{(j)}) : (γ_{1}, …, γ_{(i+1)n}, δ_{1}^{(1)}, …, δ_{i}^{(1)}, …, δ_{1}^{(j−1)}, …, δ_{i}^{(j−1)})]_{ℝ_{1}} ≤ [(δ_{1}^{(j)}, …, δ_{i}^{(j)}) : (γ_{1}, …, γ_{(i+1)n})]_{ℝ_{1}} we obtain the inequality [γ_{1}, …, γ_{(i+1)n}, δ_{1}^{(1)}, …, δ_{i}^{(1)}, …, δ_{1}^{(j)}, …, δ_{i}^{(j)}]_{ℝ_{1}} ≤ n^{2} + j(i − 1) for each 0 ≤ j ≤ n^{2} + 1.

Putting j = n^{2}+1 leads to a contradiction since [γ_{1}, …, γ_{(i+1)n}, δ_{1}^{(1)}, …, δ_{i}^{(1)}, …, δ_{1}^{(n^{2}+1)}, …, δ_{i}^{(n^{2}+1)}]_{ℝ_{1}} ≥ [δ_{1}^{(1)}, …, δ_{i}^{(1)}, …, δ_{1}^{(n^{2}+1)}, …, δ_{i}^{(n^{2}+1)}]_{ℝ_{1}} = i(n^{2} + 1) because of lemma A9, 2). □ Definition 6. A point y ∈ Ã_{i} is called i-pseudoflat if there exist the points v_{1}, …, v_{i} ∈ Ã_{i} such that | det(v_{1} − y, …, v_{i} − y)^{T} (v_{1} − y, …, v_{i} − y)| > ϵ_{1} (where (v_{1} − y_{1}, …, v_{i} − y)^{T} denotes the transposition of n × i matrix with the columns

v_{1} − y, …, v_{i} − y) and the points y + ∑_{1≤ℓ≤i}δ_{ℓ}^{(j)}(v_{ℓ} − y) ∈ Ã_{i}, 1 ≤ j ≤ n^{2} + 1.

The sub-Pfaffian set of all i-pseudoflat points denote by ϕ̃_{i}. Lemma 8. If dim(W ∩ P_{i}) = i then W ∩ P_{i} ∩ ℝ^{n} ⊂ ϕ̃_{i}. Proof. Let x̃ ∈ W ∩ P_{i} ∩ ℝ^{n}. Take arbitrary points v_{1}, …, v_{i} ∈ W ∩ P_{i} ∩ ℝ^{n} such that the vectors v_{1} − x̃, …, v_{i} − x̃ are linearly independent, then

ℝ ∋ | det(v_{1} − x̃, …, v_{i} − x̃)^{T} (v_{1} − x̃, …, v_{i} − x̃)| > 0,

22 D. GRIGORIEV AND N. VOROBJOV

obviously

| det(v_{1} − x̃, …, v_{i} − x̃)^{T} (v_{1} − x̃, …, v_{i} − x̃)| > ϵ_{1}.

The distance from a point w^{(j)} = x̃ + ∑_{1≤ℓ≤i}δ_{ℓ}^{(j)}(v_{ℓ} − x̃) ∈ ℝ_{δ}^{n} to x̃ is infinitesimal relative to ℝ_{1} for each 1 ≤ j ≤ n^{2} + 1. Lemma 3 implies that w^{(j)} ∈ Ã_{i}, 1 ≤ j ≤ n^{2} + 1, hence x̃ ∈ ϕ̃_{i} by definition 6. □

Lemma 9. st(ϕ̃_{i}) ⊂ ϕ_{i}

Proof. Let ỹ ∈ ϕ̃_{i} and v_{1}, …, v_{i} ∈ Ã_{i} satisfy definition 6. Observe that | det(st(v_{1})− st(ỹ), …, st(v_{i}) − st(ỹ))^{T} (st(v_{1}) − st(ỹ), …, st(v_{i}) − st(ỹ))| > ϵ_{1}/2, taking into account lemma A4 and that the points ỹ, v_{1}, …, v_{i} ∈ Ã_{i} ⊂ W ⊂ P are ℝ-finite (see section A2). Furthermore, st(ỹ) + ∑_{1≤ℓ≤i}δ_{ℓ}^{(j)}(st(v_{ℓ}) − st(ỹ)) ∈ st(Ã_{i}) = A_{i}, 1 ≤ j ≤ n^{2} + 1. Denote by Π the unique i-plane passing through the points st(ỹ), st(v_{1}), …, st(v_{i}). Lemma 7 entails that st(ỹ) ∈ ϕ_{i} and dim(Π ∩ A_{i}) = i. □

Let ϕ̃_{i} = ∪_{j}φ̃_{j}, ϕ_{i} = ∪_{j}φ_{ℓ} be the representations of ϕ̃_{i} and ϕ_{i}, respectively, as the unions of (necessarily sub-Pfaffian, see the section A3) connected components. Lemmas A6, A7 imply that st(φ̃_{j}) is a sub-Pfaffian connected set. Hence due to lemma 9, for each j there is ℓ such that st(φ̃_{j}) ⊂ φ_{ℓ}. For any i-facet P_{i} of P such that dim(W ∩ P_{i} ∩ ℝ^{n}) = i, lemma 8 entails that W ∩ P_{i} ∩ ℝ^{n} ⊂ ϕ̃_{i}. Take a point x ∈ W ∩ P_{i} ∩ ℝ^{n}, then x ∈ φ̃_{j} for a certain j. It follows that st(φ̃_{j}) ⊂ φ_{ℓ} for a suitable ℓ, thus x = st(x) ∈ st(φ̃_{j}) ⊂ φ_{ℓ}. Due to lemma 6, φ_{ℓ} ⊂ P_{i}. So, to any facet P_{i} such that dim(W ∩ P_{i} ∩ ℝ^{n}) = i, corresponds (not necessary unique) connected component φ̃_{j}, and to different such i-facets P_{i}, P′_{i} correspond different connected components, respectively. Thus, we obtain the following lemma.

Lemma 10. The number of i-facets P_{i} such that dim(W ∩ P_{i} ∩ ℝ^{n}) = i, does not exceed the number of connected components of ϕ̃_{i}.

Observe that ϕ̃_{i} can be defined by a Pfaffian formula ψ having a prefix with only existential quantifiers. Moreover, the prefix contains O(n^{4}) quantifiers, since for

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 23

each of O(n^{2}) points v_{1}, …, v_{i}, y + ∑_{1≤ℓ≤i}δ_{ℓ}^{(j)}(v_{ℓ} − y), 1 ≤ j ≤ n^{2} + 1, the formula

ψ expresses the condition of membership to the set Ã_{i} (see definition 6), which, in its turn, requires O(n^{2}) existential quantifiers (see definitions 2, 3), namely for the coordinates of the points y_{1}, …, y_{n}. The polynomials, occurring in ψ, and the polynomials of the type g_{v,j}, occurring in the definition of Pfaffian functions u_{0}, …, u_{K} (see the beginning of the section 1), have the degrees less than O(dn) (cf. (0)). The number of all these polynomials (i.e., the number of atomic subformulas of ψ) can be bounded by n^{O(1)}K (see lemma 1 and definitions 2, 3). Therefore, the number of all connected components of the sub-Pfaffian set ϕ̃_{i} does not exceed 2^{K^{2}}(dn K)^{O(K+n^{4})}, due to corollary A2. Together with lemma 10 this implies the following lemma. Lemma 11. The number of i-facets P_{i} such that dim(W ∩ P_{i} ∩ ℝ^{n}) = i, does not exceed 2^{K^{2}}(dn K)^{O(K+n^{4})}.

In order to complete the proof of the theorem one observes that the Pfaffian computation tree T contains at most 3^{K} branches and for each 0 ≤ i ≤ n − 1 for each i-facet P_{i} there is a branch of T such that dim(W′ ∩ P_{i} ∩ ℝ^{n}) = i where W′ is the accepting set corresponding to this branch. Hence N ≤ 3^{K}2^{K^{2}}(dn K)^{O(K+n^{4})}. Together with the assumption N ≥ (dn)^{Ω(n^{4} log d)}, this entails the inequality K ≥ Ω(\sqrt{log N}). □

24 D. GRIGORIEV AND N. VOROBJOV

APPENDIX. Sub-Pfaffian sets

A1. Gabrielov’s theorem and Khovanskii’s bound.

In this section we give definitions and describe some properties of concepts related to Pfaffian functions and to the subsets of ℝ^{n} defined by these functions. We skip all the proofs which could be found elsewhere.

The concept of Pfaffian function was introduced by Khovanskii [19, 20], who had established their fundamental properties. Definition A1. A subset A ⊂ ℂ^{n} is called complex analytic variety if any point of ℂ^{n} has a neighbourhood U such that the intersection A ∩ U coincides with the set {g_{i} = ⋯ = g_{k} = 0} ∩ U where g_{i}, …, g_{k} are complex analytic (holomorphic) functions on U (see e.g. [21]).

We say that a real analytic function f has a domain G ⊂ ℝ^{n}, if there is an open subset G ⊂ ℝ^{n} such that f is defined on G and G ⊂ G. Definition A2. (a) A Pfaffian chain of the length r and degree d_{1} ≧ 1 is a sequence of real analytic functions f_{1}, …, f_{r} with the following properties.

1. For each 1 ≦ j ≦ r there exists a complex analytic function f̃_{j} defined in a subset G̃_{j} ⊂ ℂ^{n}, such that ℂ^{n} ∖ G̃_{j} is a complex analytic variety , and f_{j} is the restriction of f̃_{j} on ℝ^{n}.

Observe that as real analytic function f_{j} has a domain G_{j} ⊂ G̃_{j} ∩ ℝ^{n}.

Let G̃ = ∩_{1≦j≦r}G̃_{j} and G = ∩_{1≦j≦r}G_{j}.

2. Every f_{j}, 1 ≦ j ≦ r satisfies a Pfaffian equation

df_{j}(X) = ∑_{1≦i≦n} g_{ij}(X, f_{1}(X), …, f_{j}(X))dX_{i}

for 1 ≦ j ≦ r. Here X = (X_{1}, …, X_{n}), g_{ij} ∈ ℝ[X, Y_{1}, …, Y_{j}], deg_{X,Y_{1},...,Y_{j}}(g_{ij}) ≦ d_{1}.

(b) A function f(X) = P (X, f_{1}(X), …, f_{r}(X)), where P ∈ ℝ[X, Y_{1}, …, Y_{r}], deg_{X,Y_{1},...,Y_{r}}(P) ≦ d_{2} is called a Pfaffian function (with a Pfaffian chain f_{1}, …, f_{r}) of length r and

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 25

degree d = d_{1} + d_{2}.

Note that our definition of a Pfaffian function is more restrictive than a usual one (see [19, 20]) due to the requirement of existence of f̃_{j}. Examples. (the exposition follows [8])

(1) Pfaffian function of the length 0 and degree d + 1 are polynomials of degree not exceeding d.

(2) The exponential function f(X) = e^{aX} is Pfaffian of the length 1 and degree 2, with G̃ = ℂ, G = ℝ, due to the equation

df(X) = af(X)dX.

(3) The function f(X) = 1/X is Pfaffian of the length 1 and degree 3 with G̃ = {X ≠ 0} ⊂ ℂ, G = {X ≠ 0} ⊂ ℝ, due to the equation df(X) = −f^{2}(X)dX.

(4) Logarithm f(X) = ln(X) is Pfaffian of length 2 and degree 3 with G̃ = {X ≠ 0} ⊂ ℂ, G = {X > 0} ⊂ ℝ,

df(X) = g(X)dX, dg(X) = −g^{2}(X)dX

where g(X) = 1/X.

(5) Tangent f(X) = tan (X) is Pfaffian of the length 1 and degree 3 with

G̃ = ⋂_{k∈ℤ} \{X ≠ \frac{π}{2} + kπ\} ⊂ ℂ, G = G̃ ∩ ℝ,

due to the equation df(X) = (1 + f^{2}(X))dX.

(6) Cosine cos(X) is Pfaffian of the length 2 and degree 3 with

G̃ = ⋂_{k∈ℤ} {X ≠ π + 2kπ} ⊂ ℂ, G = G̃ ∩ ℝ,

due to the equations

cos(X) = 2f(X) − 1, df(X) = −f(X)g(X)dX, dg(X) = 1/2(1 + g^{2}(X))dX,

where f(X) = cos^{2}(X/2) and g(X) = tan (X/2).

(7) Sine f(X) = sin(X) is Pfaffian of the length 3 and degree 3 in

G̃ = ⋂_{k∈ℤ} {X ≠ π + 2kπ} ⊂ ℂ, G = G̃ ∩ ℝ,

due to the equations df = g(X)dx where g(X) = cos(X).

Let us now list some elementary properties of Pfaffian functions, describing the behaviour of their parameters under the basic operations (proofs are simple, see e.g. [8]).

(1) The sum and the product of two Pfaffian functions f_{1} and f_{2} of length r_{1} and r_{2}, degrees d_{1} and d_{2}, with G̃ = H̃_{1}, and G̃ = H̃_{2}, G = H_{1}, G = H_{2} respectively, are Pfaffian functions of the lengths r_{1} + r_{2}, degree d_{1} + d_{1} and with G̃ = H̃_{1} ∩ H̃_{2}, G = H_{1} ∩ H_{2} for both the sum and the product. If two Pfaffian functions are defined by the same Pfaffian chain of the length r, the length of the sum and the product is also r.

(2) A partial derivative of a Pfaffian function of the length r and the degree d is a Pfaffian function of the length r and degree 2d.

(3) Let X = (X_{1}, …, X_{n}), Z = (Z_{1}, …, Z_{ℓ}) be tuples of variables and f be a Pfaffian function in X, Z of the length r_{1}, degree d_{1} and with G̃ = H̃_{1} ⊂ ℂ^{n+ℓ}, G = H_{1} ⊂ ℝ^{n+ℓ}.

Let h = (h_{1}, …, h_{ℓ}) be an ℓ-tuple of Pfaffian functions in X of length r_{2}, degree d_{2}, with a common Pfaffian chain, with G̃ = H̃_{2} ⊂ ℂ^{n}, G = H_{2} ⊂ ℝ^{n}, such that (x, h(x)) ∈ H_{1} for all x ∈ H_{2}. Then the complex analytic function g̃ ≡ f̃(X, h̃(X)) (see (a), 1 of the Definition A2) is defined in a subset H̃_{3} ⊂ ℂ^{n} such that ℂ^{n} ∖ H̃_{3} is a complex analytic variety of a dimension smaller than n. Indeed, the preimage of the complex analytic variety ℂ^{n+ℓ} ∖ H̃_{1} in ℂ^{n} ∖ H̃_{2}, under the map h̃, is also a complex analytic variety different from ℂ^{n} since g̃ is a composition of analytic functions. Therefore, the dimension of this preimage is less than n (see [21]). An easy computation (see [8]) shows that g ≡ f(X, h(X)) is a Pfaffian function in G_{2} of the length r_{1} + r_{2} and degree d_{1}d_{2}.

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 27

Lemma A1. Let f be a Pfaffian function with G ⊂ ℝ^{n} and L ⊂ ℝ^{n} be a p-plane. If there exist x ∈ G ∩ L and r, 0 < r ∈ ℝ such that f vanishes in the intersection L ∩ B_{x}(r) then f vanishes in G ∩ L (here B_{x}(r) denotes an open n-dimensional ball centered at x with radius r).

Proof. Consider complex analytic function f̃corresponding to f as in the Definition A2, and the complex p-plane L̃, defined in ℂ^{n} by the same system of linear equations as L. Since L̃ is an irreducible complex analytic variety, either it is contained in the variety ℂ^{n} ∖ G̃ or the complex dimension dim_{ℂ}(L̃ ∩ (ℂ^{n} ∖ G̃)) < dim_{ℂ}(L̃) (by the dimension of intersection theorem, see [21]). The first alternative is impossible because x ∈ L ⊂ L̃. Since dim(L ∩ B_{x}(r)) = p, the second alternative implies that the complex analytic function f̃ is defined on p-plane L̃ everywhere except a subset L̃ ∖ G̃ of a dimension less than p, and vanishes on a subset of complex dimension p. Since G̃ ∩ L̃ is connected in the topology with the base of all open balls of L̃, treated as 2p-dimensional real space, we conclude that f̃ vanishes on L̃ ∩ G̃. Hence f̃ is identically zero on L̃. It follows that the restriction f of f̃ vanishes on G ∩ L ⊂ ℝ^{n}. □

Next we define by induction two closely linked notions: quantifier-free Pfaffian formula, semi-Pfaffian set. Again our definitions will be more restrictive than the original ones (see [19, 20, 7]).

Definition A3. Let h_{0} be a Pfaffian chain of length 1, with h_{0} defined in ℝ^{n}. A quantifier-free formula of rank 0 is an expression of the form

Φ^{(0)} = ⋁_{1≦i≦s_{0}}(f_{i1}^{(0)} = ⋯ = f_{ik_{i}^{(0)}}^{(0)} = 0 & g_{i1}^{(0)} > 0 & ⋯ & g_{iℓ_{i}^{(0)}}^{(0)} > 0), (1)

where f_{ij}^{(0)}, g_{ij}^{(0)} are Pfaffian functions (called atomic functions), with h_{0} as a common Pfaffian chain (see Definition A2(b)), thus, in particular, f_{ij}^{(0)}, g_{ij}^{(0)} are defined in ℝ^{n}. Suppose that we had already defined a concept of a quantifier-free Pfaffian formula χ^{(ℓ)} of rank ℓ, 0 ≦ ℓ ∈ ℤ. A semi-Pfaffian set W ⊂ ℝ^{n}, determined by

28 D. GRIGORIEV AND N. VOROBJOV

χ^{(ℓ)} is the set of all points x ∈ ℝ^{n}, satisfying χ^{(ℓ)}. We write W = {χ^{(ℓ)}}. A quantifier-free Pfaffian formula of the rank ℓ + 1 is of the form

Φ^{(ℓ+1)} = ⋁_{1≦i≦s_{ℓ+1}}(f_{i1}^{(ℓ+1)} = ⋯ = f_{ik_{i}^{(ℓ+1)}}^{(ℓ+1)} = 0 & g_{i1}^{(ℓ+1)} > 0 & ⋯ & g_{iℓ_{i}^{(ℓ+1)}}^{(ℓ+1)} > 0),

where f_{ij}^{(ℓ+1)}, g_{ij}^{(ℓ+1)} are Pfaffian functions with the common Pfaffian chain h_{0}, …, h_{ℓ+1}. Here the function h_{ℓ+1} is defined in a domain G which is a closure of a semi-Pfaffian set of the kind {χ^{(ℓ)}}, where χ^{(ℓ)} is a quantifier-free Pfaffian formula of the rank ℓ. Functions f_{ij}^{(ℓ+1)}, g_{ij}^{(ℓ+1)}, together with all atomic functions occuring in the description of χ^{(ℓ)} are called atomic functions of Φ^{(ℓ+1)}. Example.

The set {tan(X) = 0 & a < X < b} ⊂ ℝ, where −π/2 < a < b < π/2, is semi-Pfaffian, defined by a quantifier-free Pfaffian formula. On the other hand, the set {tan(X) = 0} ∩ ⋃_{k∈ℤ}{a + kπ < X < b + kπ} ⊂ ℝ for −π/2 < a < b < π/2 (cf. Example (5) above) is not semi-Pfaffian. Definition A4. Fix a certain R, 0 < R ∈ ℝ and let K^{n} ⊂ ℝ^{n} be the n-dimensional cube centered at the origin and having an edge with length 2R. A Pfaffian formula is an expression of the form ψ = Q_{1}Y_{1}Q_{2}Y_{2} … Q_{t}Y_{t}(Φ) where Φ is a quantifier-free Pfaffian formula of arbitrary rank (called quantifier-free part of ψ) with atomic functions in n + t variables Y_{1}, …, Y_{t}, X_{1}, …, X_{n} and Q_{j}, 1 ≦ j ≦ t are quantifiers ∃ or ∀, each restricted on the interval (−R, R) ⊂ ℝ. A sub-Pfaffian set V ⊂ ℝ^{n}, determined by ψ, is the set of all points x ∈ K^{n}, satisfying ψ. We write V = {ψ}.

We say that two Pfaffian formulas ψ, ψ′ are equivalent if {ψ} = {ψ′}. Definition A5. The local dimension dim_{x}(V) of a set V at a point x ∈ V is the maximal p, 0 ≦ p ∈ ℤ such that the linear projection of a neighbourhood of x in V onto a coordinate p-subspace (along all the rest of coordinates) contains a p-dimensional ball. The dimension dim(V) of V is the maximal value dim_{x}(V) for all x ∈ V.

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 29

Definition A6. A point x of a set V ⊂ ℝ^{n}, with dim(V) = p, is called analytically nonsingular (or nonsingular) if a neighbourhood of x in V is analytically diffeomorphic (respectively, C^{1}-diffeomorphic) to an open p-dimensional ball. Denote by V_{a}^{0} (or, by V^{0}) the set of all analytically nonsingular (respectively, nonsingular) points of V. The points of the set V_{a}^{∗} = V ∖ V_{a}^{0} (respectively V^{∗} = V ∖ V^{0}) are called analytically singular (respectively, singular).

For a set V ⊂ ℝ^{n} denote by cl(V) its closure in the topology with a base of all open balls in ℝ^{n}.

Definition A7. For a set V ⊂ ℝ^{n} the disjoint family {V_{i}} of subsets V_{i} ⊂ V is called a smooth stratification of V if

1. V = ∪_{i} V_{i}

2. each V_{i}, called a stratum, is an analytic manifold in ℝ^{n}

3. if V_{i} ∩ cl(V_{j}) ≠ ∅, then V_{i} ⊂ cl(V_{j}) and dim(V_{i}) < dim V_{j}.

Proposition A1. ([16, 26]) For any sub-Pfaffian set V ⊂ ℝ^{n} there exists a finite smooth stratification.

Corollary A1. dim(V^{∗}) < dim(V).

Proof. The inequality dim(V_{a}^{∗}) < dim(V) directly follows from Proposition A1, the inequality dim(V^{∗}) ≦ dim(V_{a}^{∗}) follows from the obvious inclusion V^{∗} ⊂ V_{a}^{∗}. □

Lemma A2. For a sub-Pfaffian set V ⊂ ℝ^{n} the subsets V^{0} and V^{∗} are sub-Pfaffian.

Proof. The sets V^{0} and V^{∗} can be described by appropriate Pfaffian formulas involving a Pfaffian formula defining V. □

Definition A8. For a set V ⊂ ℝ^{n} the boundary ∂V is a subset of all points x ∈ ℝ^{n} such that for every r, 0 < r ∈ ℝ, the intersections B_{x}(r) ∩ V ≠ ∅, B_{x}(r) ∩ (ℝ^{n} ∖ V) ≠ ∅.

30 D. GRIGORIEV AND N. VOROBJOV

Lemma A3. For a sub-Pfaffian set V ⊂ ℝ^{n} the dimension dim(∂V) ≦ n − 1.

Proof. Let {V_{i}} be a finite smooth stratification of V, see Proposition A1. Suppose first that dim(V) < n. Then, the closure cl(V) = ∪_{i} cl(V_{i}) = ∪_{i} ∂V_{i} = ∂V. On the other hand, dim(cl(V)) = dim(V) [7], hence the lemma is valid in this case.

Now let dim(V) = n. The set V is representable as V = V_{max} ∪ V_{min}, where V_{max} is the union of all n-dimensional strata of V, and V_{min} is the union of the remaining strata (of smaller dimensions). Then

dim(∂V) ≦ dim(∂V_{max} ∪ ∂V_{min}) = dim((cl(V_{max}) ∖ V_{max}) ∪ ∂V_{min})
= max{dim(cl(V_{max}) ∖ V_{max}), dim(∂V_{min})}.

According to [7], dim(cl(V_{max}) ∖ V_{max}) < dim(V_{max}). The inequality dim(∂V_{min}) ≦ n − 1 was proved before. □

Definition A9. Let ψ be a Pfaffian formula having N atomic Pfaffian functions in n variables with the same Pfaffian chain of length r and degrees less than d. The 4-tuple (N, n, r, d) is called the format of ψ.

Proposition A2. ([7], theorem 2) For a Pfaffian formula ψ of a format (N, n, r, d) there exists an equivalent formula ψ′ having only existential quantifiers, and of the format (N′, n′, r′, d′), where the values N′, n′, r′, d′ are bounded from above by the value of a suitable function in N, n, r, d.

Proposition A3. ([7], theorem 1) For a sub-Pfaffian set {ψ} ⊂ ℝ^{n} with a Pfaffian formula ψ of a format (N, n, r, d), any of its connected components can be defined by a Pfaffian formula of a format (N′, n′, r′, d′), where the values N′, n′, r′, d′ are bounded from above by the value of an appropriate function in N, n, r, d.

Proposition A4. ([19, 20]) The number of the connected components of a semi-Pfaffian set {Φ} defined by a quantifier-free formula Φ of the format (N, n, r, d) does not exceed 2^{r^{2}}n^{O(r)}(Nd)^{O(r+n)}.

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 31

There is a generally adopted conjecture that under the hypothesis of the Proposition A4 the bound n^{O(r)}(Nd)^{O(r+n)} is actually true. Corollary A2. The number of the connected components of a sub-Pfaffian set {ψ}, defined by a formula ψ of the format (N, n, r, d) in which only existential quantifiers can occur, does not exceed 2^{r^{2}}n^{O(r)}(Nd)^{O(r+n)}. Proof. It is sufficient to note that the number of the connected components of a projection of a set does not exceed the number of the connected components of the set itself. □ Corollary A3. The number of the connected components of an arbitrary sub-Pfaffian set {ψ}, defined by a formula ψ of a format (N, n, r, d) is finite, moreover, is bounded from above by the value of a certain function in N, n, r, d. Proof. Apply to ψ successively the Proposition A3 and the Corollary A2. □ Corollary A4. Zero-dimensional sub-Pfaffian set in ℝ^{n} is finite. A sub-Pfaffian set in ℝ^{1} is a finite union of points and (open, closed or semi-closed) intervals. In each case the number of the points or the intervals is bounded from above by the value of a certain function in the format of a formula representing the sub-Pfaffian set. Proof. Directly follows from Lemma A2 and Corollary A3. □ A2. Sub-Pfaffian sets over nonstandard extensions of reals.

In the main text of the paper we consider the extensions of the field ℝ with “nonstandard” (in particular infinitesimal) elements. The following digest from nonstandard analysis is taken from [27] , for a detailed exposition see [6].

There exists a sequence of ordered fields

ℝ_{0} = ℝ ⊂ ℝ_{1} ⊂ ℝ_{2} ⊂ ⋯ ⊂ ℝ_{k} ⊂ …

in which the field ℝ_{k}, k ≧ 1 contains an element ε_{k} > 0 infinitesimal relative to the elements of ℝ_{k−1} (i.e., for every positive element a ∈ ℝ_{k−1} the inequaltiy ε_{k} < a

32 D. GRIGORIEV AND N. VOROBJOV

is true). In addition, for every function φ : ℝ_{k−1}^{n} ⟶ ℝ_{k−1} there exists a natural extension, being a function φ from ℝ_{k}^{n} to ℝ_{k}. It follows, invoking characteristic functions, that each subset S ⊂ ℝ_{k−1}^{n} has a natural extension to ℝ_{k}^{n}. We say that ℝ_{j} is a nonstandard extension of ℝ_{i} for 0 ≦ i < j.

Consider the language L_{k}, k ≧ 0 of the first order predicate calculus, in which the set of all function symbols is in a bijective correspondence with the set of all functions of several arguments from ℝ_{k} taking values in ℝ_{k} and the only predicate is the equality relation. We shall say that the closed (i.e., containing no free variables) formula Φ of the language L_{k} is true in ℝ_{k}, k ≧ 0, if and only if the statement expressed by this formula with respect to ℝ_{k} is true. The following “transfer principle” is valid: for all integers 0 ≦ i < j the closed formula Φ of L_{i} is true in ℝ_{i} if and only if it is true in ℝ_{j}.

An element z ∈ ℝ_{k}, k ≧ 1 is called infinitesimal relative to ℝ_{j}, j < k, if for every 0 < w ∈ ℝ_{j} the inequality |z| < w is valid. An element z ∈ ℝ_{k} is called infinitely large, if z = 1/z′, where z′ is infinitesimal. If z ∈ ℝ_{k} is not infinitely large relative to ℝ_{j}, z is called ℝ_{j}-finite.

One can prove [6] that if an element z ∈ ℝ_{k} is ℝ_{j}-finite then there exist unique elements z_{1} ∈ ℝ_{j} and z_{2} ∈ ℝ_{k}, where z_{2} is infinitesimal relative to ℝ_{j}, such that z = z_{1} + z_{2}. In this case z_{1} is called the standard part of z (relative to ℝ_{j}) and is denoted by z_{1} = st_{j}(z). One can extend the operation st_{j} (componentwise) to vectors from ℝ_{k}^{n} and (elementwise) to subsets of ℝ_{k}^{n}.

In what follows, all the functions φ we shall consider in ℝ_{k}^{n}, k ≧ 0, will be Pfaffian. By this we mean that for each φ there exists a Pfaffian function φ′ definable over ℝ (i.e., in the sense of the Definition A2) such that φ is the result of a replacement of some variables in φ′ by some elements of ℝ_{k}.

Moreover, we assume that the domain G ⊂ ℝ_{k}^{n} of φ is a sub-Pfaffian set, defined by a Pfaffian formula Π with atomic functions definable over ℝ and some variables replaced by elements from ℝ_{k}. We say that φ is definable over ℝ_{k}.

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 33

For any ℓ > k, the same function φ′, formula Π and the replacements determine the function φ^{(ℓ)} : G^{(ℓ)} ⟶ ℝ_{ℓ} which coincides with φ in ℝ_{k}^{n} and is called the completion of φ over ℝ_{ℓ}, similarly G^{(ℓ)} ⊂ ℝ_{ℓ}^{n} (determined by Π) is called the completion of G over ℝ_{ℓ}.

Basic notions, introduced in section A1 can be naturally extended to a nonstandard field ℝ_{k} for k > 0. Thus, we shall consider semi-Pfaffian sets, sub-Pfaffian sets, Pfaffian formulas, determined in ℝ_{k}^{n} by Pfaffian functions definable over ℝ_{k}. In this case we say that the sets and formulas are definable over ℝ_{k}.

If a sub-Pfaffian set W ⊂ ℝ_{k}^{n} is determined in ℝ_{k}^{n} by a Pfaffian formula Φ with atomic subformulas definable over ℝ_{k} then the sub-Pfaffian set in ℝ_{ℓ}^{n}, ℓ > k determined by the same formula in which the atomic functions are replaced by their completions is called the completion of W and is denoted by W^{(ℓ)}.

Some of the basic statements proved earlier in this Appendix can be extended (using the transfer principle) to the fields ℝ_{k} for k > 0. This obviously concerns the statements: lemma A1, corollary A1, lemma A2, lemma A3, proposition A2, corollary A4. Propositions A3, A4, Corollaries A2, A3, about the estimates of the connected components are also extendable (see below).

The following lemma illustrates a use of the transfer principle and the notion of the standard part. Lemma A4. Let f : S → ℝ_{k} be a Pfaffian function defined in a sub-Pfaffian bounded set S ⊂ ℝ_{k}^{n}. Denote by S^{(k+1)} the completion of S over ℝ_{k+1} and by f^{(k+1)} the completion of f. Then for any point x ∈ S^{(k+1)} such that B_{x}(r) ⊂ S^{(k+1)} for some r, 0 < r ∈ ℝ_{k}, the standard part st_{k}(f^{(k+1)}(x)) = f(st_{k}(x)). If in addition, there do not exist y ∈ S and R, 0 < R ∈ ℝ_{k} such that f(z) = 0 for all z ∈ B_{y}(R), and besides f(w) ≥ 0 for all w ∈ S, then

st_{k}({f^{(k+1)} = ε_{k+1}}) = {f = 0}.

Proof. First, observe that any Pfaffian function is continuous. This is true for a Pfaffian function φ definable over ℝ (since φ is analytic, see definition A2), then the

34 D. GRIGORIEV AND N. VOROBJOV

Pfaffian formula of the language L_{0} expressing continuity, is valid for the completion φ^{(ℓ)}, ℓ ≥ 0, due to the transfer principle, and hence, it is valid as well for Pfaffian functions definable over arbitrary ℝ_{ℓ}. The equality st_{k}(f^{(k+1)}(x) = f(st_{k}(x)) and thereby the inclusion st_{k}({f^{(k+1)} = ε_{k+1}}) ⊂ {f = 0} follows from continuity of f and f^{(k+1)}.

Now let x ∈ {f = 0}. Take r, 0 < r ∈ ℝ_{k} such that B_{x}(r) ⊂ S (cf. definition A2). Consider a sub-Pfaffian set D = {∥x − z∥^{2} : z ∈ S^{(k+1)}, f^{(k+1)}(z) = ε_{k+1}} ⊂ ℝ_{k+1}. If it is empty, then f^{(k+1)} is less than ε_{k+1} everywhere on the ball B_{x}(r), by virtue of the theorem on intermediate values of continuous functions which holds for Pfaffian functions by the transfer principle, hence f vanishes everywhere on the ball B_{x}(r) ∩ ℝ_{k}^{n} and we get a contradiction. Due to the Corollary A4 the set D consists of a finite union of points and intervals. Denote by u the minimum of these points and endpoints of these intervals. If st_{k}(u) > 0 then the function f^{(k+1)} on the ball B_{x}(\sqrt{u}) ∩ B_{x}(r) takes the values less than ε_{k+1} because of continuity of f^{(k+1)}. Therefore, f vanishes everywhere on the ball

B_{x}(\sqrt{u}) ∩ B_{x}(r) ∩ ℝ_{k}^{n} ⊃ B_{x}(st_{k}(\sqrt{u})/2) ∩ B_{x}(r) ∩ ℝ_{k}^{n}

with a positive radius from ℝ_{k} (sf. above). The obtained contradiction shows that st_{k}(u) = 0. Take any point w such that f^{(k+1)}(w) = ε_{k+1} and ∥w −x∥^{2} ≤ u+ε_{k+1}, then st_{k}(w) = x. □

Lemma A5. Let a sub-Pfaffian set W ⊂ ℝ_{k}^{n}, defined by a Pfaffian formula Π, be finite. Then the completion W^{(ℓ)} ⊂ ℝ_{ℓ}^{n}, ℓ > k of W coincides with W.

Proof. Let W = {x^{(1)}, …, x^{(t)}}. Then the following formula of the language L_{k} is true over ℝ_{k}:

&_{1≦i≦t} Π(x^{(i)}) & ∀X_{1} ⋯ ∀X_{n} ( &_{1≦i≦t} ((X_{1}, …, X_{n}) ≠ x^{(i)}) ⇒ ℸΠ(X_{1}, …, X_{n})) .

By the transfer principle, this formula is also true over ℝ_{ℓ}. □

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 35

For a Pfaffian function f : G ⟶ ℝ_{k}, G ⊂ ℝ_{k}^{n} a point x ∈ G is called the critical point of f if the gradient vector (\frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{n}} ) (x) = 0. The value f(x) is called, in this case, the critical value of f. The value which is not critical is called regular. Corollary A5. For a Pfaffian function f definable over ℝ_{k}, any element α ∈ ℝ_{ℓ} ∖ ℝ_{k} for ℓ > k cannot be a critical value of f. Proof. Observe that the set Γ_{k} ⊂ ℝ_{k} of all critical values of f is sub-Pfaffian and definable over ℝ_{k}.

Suppose first that k = 0. Then Corollary A4 implies that Γ_{0} consists of a finite number of points and segments. Moreover, by Sard’s theorem, Γ_{0} actually consists of a finite number of points. For all sub-Pfaffian sets of the form Γ_{0} and having a fixed format the latter statement can be expressed by a formula of the language L_{0} (taking into the account that the number of points is bounded via the format). Hence, by the transfer principle the statement is true for any k ≧ 0, i.e., Γ_{k} is finite.

According to lemma A5, the completion Γ_{k}^{(ℓ)} = Γ_{k} ⊂ ℝ_{k}, and, therefore α ∉ Γ_{k}^{(ℓ)}. □ Corollary A6. Let a Pfaffian function

f : G ⟶ ℝ_{k}, G ⊂ ℝ_{k}

be definable over ℝ_{k} and f ≢ 0 on G. If α ∈ ℝ_{ℓ} ∖ ℝ_{k} for ℓ > k then f(α) ≠ 0. Proof. According to lemma A1 and corollary A4, the set W of roots of f is finite. Apply lemma A5 to W. □ A3. Connected components of sub-Pfaffian sets over non-standard fields.

Now we are going to extend the notion of the connected component to the sub-Pfaffian sets definable over ℝ_{k}^{n}, k ≧ 1. Observe that a direct way to do this, starting with the topology on ℝ_{k}^{n} with the base of all open balls, would lead to unnatural objects, e.g., the segment [0, 1] ⊂ ℝ_{k} is not connected in this topology. The analogous construction of connected components for semialgebraic sets over non-standard fields was described in [14].

36 D. GRIGORIEV AND N. VOROBJOV

Let V = {Π} be a sub-Pfaffian set in ℝ^{n} determined by a Pfaffian formula Π. The Proposition A3 and the Corollary A3 imply the existence of a function ω : ℕ ⟶ ℕ such that if the elements of the 4-tuple format of Π are bounded from above by some N ∈ ℕ, then:

1. The number of the connected components does not exceed ω(N);

2. For each connected component V_{i} of V there exists a Pfaffian formula Π_{i} of a format with components not exceeding ω(N), such that V_{i} = {Π_{i}}.

It follows that for a given positive integer N, there exists a Pfaffian formula Ω_{N} of the language L_{0}, expressing the existence of a decomposition of any sub-Pfaffian set V = {Π} of the format of Π less than N into its connected components

V = ⋃_{i}{Π_{i}}

such that the format of every Π_{i}, and the number of Π_{i}, are less than ω(N). Moreover, the formula Ω_{N} states that for each pair of indices i_{1} ≠ i_{2} the components {Π_{i_{1}}} and {Π_{i_{2}}} are “separated”, i.e. the following Pfaffian formula of the language L_{0} is valid:

∀ (x ∈ {Π_{i_{1}}})∃z > 0∀ (y ∈ {Π_{i_{2}}})(∥x − y∥ ≧ z).

Besides, the formula Ω_{N} claims the connectedness of every component {Π_{i}}, this means that there do not exist two “separated” sub-Pfaffian subsets of {Π_{i}}, each determined by a Pfaffian formula with format less than ω(ω(N)).

Apart from that, for given positive integers N, M one can verify a formula Ω_{N ,M} of language L_{0} expressing the following statement. If a sub-Pfaffian set {Π} (where the format of Π is less than N) can be represented as a union of more than one and less than M pairwise “separated” sub-Pfaffian sets, each being determined by a Pfaffian formula of L_{0} of a format less than M, then {Π} can be represented as a union of more than one and less than ω(N) pairwise “separated” connected sub-Pfaffian sets, each being determined by a Pfaffian formula of L_{0} of a format less than ω(N).

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 37

Applying the transfer principle to the formulas Ω_{N}, Ω_{N ,M} for all positive integers N , M, we conclude that any sub-Pfaffian set, defined over ℝ_{k}, k ≧ 0, can be uniquely represented as a union of its pairwise “separated” connected components, moreover, each component is sub-Pfaffian and is connected, i.e. cannot be represented as a union of more than one pairwise “separated” sub-Pfaffian sets.

Having defined the connected components of a sub-Pfaffian set definable over ℝ_{k}, k ≧ 0, one can use the transfer principle to extend to this set Propositions A3, A4 and Corollaries A2 and A3. Lemma A6. Let V ⊂ ℝ_{k}^{n}, W ⊂ ℝ_{k+t}^{n} be two sub-Pfaffian sets and V = st_{k}(W). Let

V = ⋃_{m} V_{m}, W = ⋃_{ℓ} W_{ℓ}

be the decompositions of the sets V, W into their connected components. Then, for every index m there exist such indices ℓ_{1}, …, ℓ_{s} that st(W_{ℓ_{1}} ∪ ⋯ ∪ W_{ℓ_{s}}) = V_{m}. Moreover, for each ℓ there exists the unique index m such that st(W_{ℓ}) ⊂ V_{m}. Proof. Is almost verbatim repetition of the proof of the lemma 1 in [14]. □

For a sub-Pfaffian set W ⊂ ℝ_{k}^{n}, k ≧ 0, we denote by cl(W) its closure in the topology in ℝ_{k}^{n} with the base of all open balls. Lemma A7. (cf. [25]) Let W_{Y} = {ψ_{Y} } ⊂ ℝ_{k}^{n+t} be a sub-Pfaffian set determined by a Pfaffian formula ψ_{Y} in which the atomic Pfaffian functions are in variables X_{1}, …, X_{n}, Y_{1}, …, Y_{t}, Z_{1}, …, Z_{s}, where first n + t variables occur free. Let, for the sequence of fields ℝ_{k} ⊂ ℝ_{k+1} ⊂ ⋯ ⊂ ℝ_{t}, the element ε_{k+i+1} be infinitesimal relative to ℝ_{k+i} for 0 ≦ i ≦ t − 1. Denote by ψ_{ε} the Pfaffian formula which is the result of the replacement of Y_{ℓ} by ε_{k+ℓ} for every 1 ≦ ℓ ≦ t; let W_{ε} = {ψ_{ε}} ⊂ ℝ_{k+t}^{n}. Then the set V = st_{k}(W_{ε}) ⊂ ℝ_{k}^{n} is sub-Pfaffian. Proof. It is sufficient, due to Proposition A2, to prove the lemma for the case ψ_{Y} = ∃Z_{1}, … ∃Z_{s}(Φ_{Y}) with quantifier-free Φ_{Y}. Observe that W_{ε} = π{Φ_{ε}} where Φ_{ε} is quantifier-free formula, being the result of the replacement of Y_{ℓ} by ε_{k+ℓ},

38 D. GRIGORIEV AND N. VOROBJOV

1 ≦ ℓ ≦ t in Φ_{Y}, and π is the linear projection map on the subspace of coordinates X_{1}, …, X_{n} along the coordinates Z_{1}, …, Z_{s}.

The proof can be conducted by induction on t, in which an ith induction step proves that the set st_{k+t−i}(W_{ε}) is sub-Pfaffian. It will be obvious from the formula (4) below that the output of the inductive step, namely, the set st_{k+t−i}(W_{ε}), satisfies the requirements for the set W_{ε} of the lemma, i.e., there exists a sub-Pfaffian set W′_{Y}, determined by a Pfaffian formula ψ′_{Y} in variables X_{1}, …, X_{n}, Y_{1}, …, Y_{t−i}, Z′_{1}, …, Z′_{s′}, where first n+t−i variables occur free, such that st_{k+t−i}(W_{ε}) = {ψ′_{ε}}, where ψ′_{ε} is the result of the replacement of Y_{ℓ} by ε_{k+ℓ} for every 1 ≦ ℓ ≦ t − i.

Thus, we assume that t = 1.

We can identify the sets {Φ_{ε}} and {Φ_{Y} & (Y_{1} = ε_{k+1})}.

Let us prove that

st_{k}({Φ_{Y} & (Y_{1} = ε_{k+1})}) = cl({Φ_{Y} & (Y_{1} > 0)}) ∩ {Y_{1} = 0}.  (2)

Observe that the right side of the equality (2) is a sub-Pfaffian set.

Let x ∈ st_{k}({Φ_{Y} & (Y_{1} = ε_{k+1})}), then there exists z ∈ {Φ_{Y} & (Y_{1} = ε_{k+1})} such that x = st_{k}(z). Hence, x ∈ {Y_{1} = 0}. Suppose that x ∉ cl({Φ_{Y} & (Y_{1} > 0)}). Then there exists an element r, 0 < r ∈ ℝ_{k} such that B_{x}(r) ∩ {Φ_{Y} & (Y_{1} > 0)} = ∅. This contradicts to the inclusion z ∈ {Φ_{Y} & (Y_{1} = ε_{k+1})} ⊂ {Φ_{Y} & (Y_{1} > 0)}.

Suppose now that

x ∈ cl({Φ_{Y} & (Y_{1} > 0)}) ∩ {Y_{1} = 0},

i.e. x belongs to the right side of (2).

Let us prove the following claim: for any element R, 0 < R ∈ ℝ_{k}, there exists an element α, 0 < α ∈ ℝ_{k}, such that for every β, 0 < β ∈ ℝ_{k}, β < α the intersection

B_{x}(R) ∩ {Φ_{y} & (Y_{1} = β)}

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 39

is nonempty. Indeed, since the set B_{x}(R) ∩ {Φ_{Y} & (Y_{1} > 0)} is sub-Pfaffian, and, thus has a finite number of the connected components (see the considerations preceding the lemma), there exists a connected component U of this set such that x ∈ cl(U). One can take as α the Y_{1}-coordinate of any point from U and the claim is proved.

It follows (with a help of the transfer principle) that for every fixed R, 0 < R ∈ ℝ_{k} the intersection

B_{x}(R) ∩ {Φ_{Y} & (Y_{1} = ε_{k+1})} ≠ ∅.  (3)

Observe that the set A = {∥z − x∥^{2} : z ∈ {Φ_{Y} & (Y_{1} = ε_{k+1})}} ⊂ ℝ_{k+1} is sub-Pfaffian. Due to Corollary A4, A is a finite union of points and intervals. Let w ∈ ℝ_{k+1} be the minimal among these points and the endpoints of these intervals.

Suppose that x ∉ st_{k}({Φ_{Y} & (Y_{1} = ε_{k+1})}), i.e. there does not exist z ∈ {Φ_{Y} & (Y_{1} = ε_{k+1})} such that st_{k}(z) = x. Thus, w > r_{1}^{2} for an element 0 < r_{1} ∈ ℝ_{k}. It follows that B_{x}(r_{1}) ∩ {Φ_{Y} & (Y_{1} = ε_{k+1})} = ∅. This contradicts (3) for R = r_{1}, and the equality (2) is proved.

We have:

st_{k}(W_{ε}) = st_{k}(π({Φ_{Y} & (Y_{1} = ε_{k+1})})) =
π(st_{k}({Φ_{Y} & (Y_{1} = ε_{k+1})})) = π(cl({Φ_{Y} & (Y_{1} > 0)}) ∩ {Y_{1} = 0}). (4)

The latter set is obviously sub-Pfaffian, this proves the lemma. □ Lemma A8. Let W ⊂ ℝ_{k+t}^{n} be a sub-Pfaffian set, V = st_{k}(W) ⊂ ℝ_{k}^{n}. Then dim(V) ≤ dim(W). Proof. Suppose the contrary, let dim W = ℓ − 1, dim(V) ≥ ℓ. There exists a linear projection π : ℝ_{k+t}^{n} → ℝ_{k+t}^{ℓ} definable over ℝ such that dim(π(W)) = dim(W), dim(π(V)) = ℓ, here π(V) ⊂ ℝ_{k}^{ℓ} (actually “almost any” linear projection satisfies these properties). Using the obvious identity st_{k}(π(W)) = π(st_{k}(W)) one can assume without loss of generality that dim(W) = n−1, dim(V) = n. Hence V contains a ball of a certain radius 0 < r ∈ ℝ_{k}.

40 D. GRIGORIEV AND N. VOROBJOV

Fix some integer M which we’ll specify later. Making a suitable affine transformation of the coordinates (definable over ℝ_{k}), we can assume that the following requirements are fulfilled (cf. lemma 2). The set V contains n-dimensional cube K with a side 0 < r_{1} ∈ ℝ_{k}, contained in the nonnegative ortant and having the origin as one of its nodes. Moreover, we require that for each 1 ≤ j ≤ n and a j-plane P being the intersection of any (n − j) hyperplanes of the form P_{s}^{(m)} = \{X_{s} = \frac{m}{M} r_{1}\}, 1 ≤ s ≤ n, 0 ≤ m ≤ M, the dimension dim(W ∩ P) ≤ j − 1.

Observe that the hyperplanes P_{s}^{(m)} divide K in M^{n} small cubes with sides r_{1}/M. Moreover for each 0 ≤ j ≤ n and each j-plane P the intersection P ∩ K is divided by the same way in M^{j} j-facets being j-dimensional cubes with sides r_{1}/M (we assume here that a facet contains its boundary). Note that the boundary of j-facet is the union of (j − 1)-facets. Denote by ν_{j} the number of j-facets which have common points with W. Denote by A_{j}, 0 ≤ j ≤ n the intersection of the set W ∩K with the union of all j-planes of the described form. Obviously, A_{j} is a sub-Pfaffian set. Denote by α_{j} the number of connected components of A_{j}.

We claim that ν_{j} ≤ 2(n − j + 1)ν_{j−1} + α_{j}, 1 ≤ j ≤ n. Indeed, ν_{j} ≤ ν_{j}^{(0)} + ν_{j}^{(1)}, where ν_{j}^{(0)} is the number of j-facets Q^{(0)} which have common points with the connected components C^{(0)} of A_{j} such that C^{(0)} has no common points with jfacets other than Q^{(0)}, and ν_{j}^{(1)} is the number of j-facets Q^{(1)} not satisfying this property and Q^{(1)} ∩ W ≠ ∅. Obviously, ν_{j}^{(0)} ≤ α_{j}. For j-facet Q^{(1)} take any connected component C^{(1)} of A_{j} such that C^{(1)} has common points with some jfacet different from Q^{(1)}, then C^{(1)} has a common point with a certain (j − 1)-facet R from the boundary of Q^{(1)}, attach to Q^{(1)} any such (j − 1)-facet R. Since any (j − 1)-facet R lies in the boundary of at most 2(n − j + 1) j-facets, R can be attached to at most 2(n − j + 1) j-facets. Hence ν_{j}^{(1)} ≤ 2(n − j + 1)ν_{j−1} that proves the claim.

Corollary A3 implies that there exists an integer c which depends only on the format of a Pfaffian formula defining the set W such that the number of connected

COMPLEXITY LOWER BOUNDS FOR COMPUTATION TREES 41

components of the intersection of W ∩K with any j-plane does not exceed c. Therefore, α_{j} ≤ c(M + 1)^{n−j}.

Clearly, ν_{n} = M^{n} since st_{k}(W) ⊃ K (indeed, if some n-facet does not intersect with W then its center does not belong to st_{k}(W)). Using the bound on α_{j} and the proved above claim we prove by induction on 0 ≤ j ≤ n − 1 the existence of integers c_{j} such that ν_{n−j} ≥ \frac{1}{c_{j}} M^{n} for large enough arbitrary M.

On the other hand, A_{1} consists of a finite number of points (since dim(A_{1}) = 0), hence ν_{0} ≤ α_{1}, then the proved claim (for j = 1) entails ν_{1} ≤ (2n + 1)α_{1} ≤ c′M^{n−1} for an appropriate integer c′, that leads to a contradiction for large enough M > c′c_{n−1}. □

A4. Degree of sub-Pfaffian transcendency.

Let 1 ≤ j_{1} < j_{2} and the elements γ_{1}, …, γ_{k}, θ_{1}, …, θ_{ℓ} ∈ ℝ_{j_{2}}. Denote the coordinates in ℝ_{j_{2}}^{k+ℓ} by Y_{1}, …, Y_{k+ℓ}.

Definition A10. The degree of sub-Pfaffian transcendency [(θ_{1}, …, θ_{ℓ}) : (γ_{1}, …, γ_{k})] = [(θ_{1}, …, θ_{ℓ}) : (γ_{1}, …, γ_{k})]_{ℝ_{j_{1}}} is the minimal integer s ≧ 0 such that there exists a sub-Pfaffian set S ⊂ ℝ_{j_{2}}^{k+ℓ} definable over ℝ_{j_{1}} such that (γ_{1}, …, γ_{k}, θ_{1}, …, θ_{ℓ}) ∈ S and dim(S ∩ {Y_{1} = γ_{1}, …, Y_{k} = γ_{k}}) = s.

When k = 0 we write simply [θ_{1}, …, θ_{ℓ}].

Observe that the definition correlates with the usual notion of degree of transcendency of the fields extension [F (θ_{1}, …, θ_{ℓ}, γ_{1}, …, γ_{k}) : F (γ_{1}, …, γ_{k})] replacing ℝ_{j_{1}} by a field F and taking as S an algebraic variety.

Lemma A9. 1) [θ_{1}, …, θ_{ℓ+1}] ≤ [θ_{1}, …, θ_{ℓ}] + 1;

2) [ε_{j_{1}+1}, …, ε_{j_{2}}] = j_{2} − j_{1} (the infinitesimals ε_{j} were introduced in section A2).

Proof. 1) Let S ⊂ ℝ_{j_{2}}^{ℓ} be as in the definition, then the point (θ_{1}, …, θ_{ℓ+1}) belongs to the cylinder S × ℝ_{j_{2}} ⊂ ℝ_{j_{2}}^{ℓ+1}.

2) Conduct the proof by induction on (j_{2}−j_{1}). The base of induction for j_{2}−j_{1} = 0 is trivial. For the inductive step assume the contrary and let S ⊂ ℝ_{j_{2}}^{j_{2}−j_{1}} be as in

42 D. GRIGORIEV AND N. VOROBJOV

the definition A10 such that (ε_{j_{1}+1}, …, ε_{j_{2}}) ∈ S and dim(S) = s ≤ j_{2} − j_{1} − 1. Let Y_{1}, …, Y_{j_{2}−j_{1}} be the coordinates in ℝ_{j_{2}}^{j_{2}−j_{1}}. Consider the sub-Pfaffian set S_{0} = {y : dim({Y_{1} = y} ∩ S) = s} ⊂ ℝ_{j_{2}}. Then dim(S_{0}) = 0, since dim(S) = s. Observe that S_{0} is defined over ℝ_{j_{1}}, hence, due to corollary A4, S_{0} consists of a finite number of points all belonging to ℝ_{j_{1}}. Denote S_{1} = {Y_{1} = ε_{j_{1}+1}} ∩ S ⊂ {Y_{1} = ε_{j_{1}+1}} ≃ ℝ_{j_{2}}^{j_{2}−j_{1}−1}. Then dim(S_{1}) ≤ s − 1, and one can apply the inductive hypothesis to the set S_{1}, taking into account that (ε_{j_{1}+2}, …, ε_{j_{2}}) ∈ S_{1}. □

The following lemma is an analogy of the additivity of the usual degree of transcendency: [F_{3} : F_{1}] = [F_{3} : F_{2}] + [F_{2} : F_{1}] for fields extensions F_{1} ⊂ F_{2} ⊂ F_{3}. Lemma A10. [γ_{1}, …, γ_{k}, θ_{1}, …, θ_{ℓ}] = [γ_{1}, …, γ_{k}] + [(θ_{1}, …, θ_{ℓ}) : (γ_{1}, …, γ_{k})]. Proof. Denote [γ_{1}, …, γ_{k}, θ_{1}, …, θ_{ℓ}] = m, [γ_{1}, …, γ_{k}] = p, [(θ_{1}, …, θ_{ℓ}) : (γ_{1}, …, γ_{k})] = s. First prove

1) m ≤ p + s.

Let a sub-Pfaffian set S be as in the definition A10. Consider the sub-Pfaffian set U_{1} ⊂ ℝ_{j_{2}}^{k} consisting of all the points (y_{1}, …, y_{k}) for which dim(S ∩ {Y_{1} = y_{1}, …, Y_{k} = y_{k}}) ≤ s. Then U_{1} is definable over ℝ_{j_{1}}. Due to the definition A10 there exists a sub-Pfaffian set U ⊂ ℝ_{j_{2}}^{k} definable over ℝ_{j_{1}} such that (γ_{1}, …, γ_{k}) ∈ U and dim U = p.

Denote by π : ℝ_{j_{2}}^{k+ℓ} → ℝ_{j_{2}}^{k} the natural projection onto the subspace with the coordinates Y_{1}, …, Y_{k}. Consider the sub-Pfaffian set U = S ∩ ((U ∩ U_{1}) × ℝ_{j_{2}}^{ℓ}) ⊂ ℝ_{j_{2}}^{k+ℓ}. Then U is definable over ℝ_{j_{1}}, besides (γ_{1}, …, γ_{k}, θ_{1}, …, θ_{ℓ}) ∈ U. The dimension dim(U) ≤ p + s, since dim(π(U)) ≤ dim(U) = p and for any point y ∈ π(U) we have dim(U ∩ π^{−1}(y)) ≤ s.

2) m ≥ p + s.

According to the definition A10 there exists a sub-Pfaffian set V ⊂ ℝ_{j_{2}}^{k+ℓ} definable over ℝ_{j_{1}} such that (γ_{1}, …, γ_{k}, θ_{1}, …, θ_{ℓ}) ∈ V and dim(V) = m. Denote dim(V ∩ {Y_{1} = γ_{1}, …, Y_{k} = γ_{k}}) = s_{1}. Obviously s_{1} ≥ s. Consider the sub-Pfaffian set V_{1} ⊂ ℝ_{j_{2}}^{k} consisting of all the points (y_{1}, …, y_{k}) for which dim(V ∩ {Y_{1} = y_{1}, …, Y_{k} = y_{k}}) ≥ s_{1}. Then V_{1} is definable over ℝ_{j_{1}} and (γ_{1}, …, γ_{k}) ∈ V_{1},

therefore dim V_{1} ≥ p. Arguing similarly as in 1), we get m ≥ s_{1}+dim V_{1} ≥ s+p. □

Acknowledgements. We thank A. Gabrielov for helpful discussions on sub-

Pfaffian sets.

References

1. M. Ben-Or, Lower bounds for algebraic computation trees, in: Proc. ACM Symp. on Theory of Computing (1983), 80–86.

2. Bierstone, P. Milman, Semi-analytic and sub-analytic sets, Inst. Hautes Etudes Sci. Publ. Math. 67 (1987), 5–42.

3. A. Björner, Subspace arrangements, in: Proc. of 1st European Congres of Mathematicians (Paris, 1992).

4. A. Björner, L. Lovasz, A. Yao, Linear decision trees: volume estimates and topological bounds, in: Proc. ACM Symp. on Theory of Computing (1992), 170–177.

5. A. Chistov, Fast parallel calculation of the rank of matrices over a field of arbitrary characteristics, in: Lect. Notes in Computer Science, (Springer, Berlin, 1985) Vol. 199, 63–69.

6. M. Davis, Applied nonstandard analysis (John Wiley, 1977).

7. A. Gabrielov, Existential formulas for analytic functions, Preprint 93–60, Cornell University, MSI (1993).

8. A. Gabrielov, N. Vorobjov, Complexity of stratifications of semi-Pfaffian sets, Discrete and Computational Geometry 13 (1995).

9. D. Grigoriev, Complexity of deciding Tarski algebra, J. Symb. Comput. 5 (1988), 65–108.

10. D. Grigoriev, Deviation theorems for Pfaffian sigmoids, St. Petersburg Math. J. (1994), 127–131.

11. D. Grigoriev, M. Karpinski, Lower bounds on complexity of testing membership to a polygon for algebraic, randomized and exp-log trees, Technical report TR-93–042, Intern. Computer Science Institute, Berkeley (1993).

12. D. Grigoriev, M. Karpinski, N. Vorobjov, Lower bounds on testing membership to a polyhedron by algebraic decision trees, Proc. ACM Symp. on Theory of Computing (1994).

13. D. Grigoriev, M. Singer, A. Yao, On computing algebraic functions using logarithms and exponentials, Technical Report 93-07, DIMACS (1993).

14. D. Grigoriev, N. Vorobjov, Solving systems of polynomial inequalitites in subexponential time, J. Symb. Comput. 5 (1988), 37-64.

15. D. Grigoriev, N. Vorobjov, Complexity lower bounds for computation trees with elementary transcendental function gates, Proc. IEEE Symp. on Foundations of Computer Sci. (1994), 548–552.

16. R. M. Hardt, Topological properties of sub-analytic sets, Trans. Amer. Math. Soc. 211 (1975), 57–70.

17. J. Heintz, M.-F. Roy, P. Solerno, Sur la complexité du principe de Tarski-Seidenberg, Bull. Soc. Math. France 118 (1990), 101–126.

18. J. Já Já, Computation of algebraic functions with root extractions, in: Proc. IEEE Symp. on Foundations of Computer Science (1981), 95–100.

19. A. Khovanskii, Fewnomials and Pfaff manifolds, in: Proc. Intern. Congress of Mathematicians (Warszawa, 1983), 549–564.

20. A. Khovanskii, Fewnomials, Translations of Mathematical Monographs, Amer. Math. Soc. Vol. 88 (1991).

21. S. Łojasiewicz, Introduction to complex analytic geometry (Birkhäuser, 1991).

22. F. Meyer auf der Heide, Fast algorithms for n-dimensional restrictions of hard problems, J. Assoc. Comput. Mach. 35 (1988), 740–747.

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

24. J. Renegar, On the computational complexity and the first order theory of the reals. Parts I–III, J. Symb. Comput. 13 (1992), 255–352.

25. M.-F. Roy, N. Vorobjov, Finding irreducible components of some real transcendental varieties, Computational Complexity 4 (1994), 107-132.

26. H. Sussmann, Real-analytic desingularization and sub-analytic sets: an elementary approach, Trans. Amer. Math. Soc. 317 (1990), 417–461.

27. N. Vorobjov, The complexity of deciding consistency of systems of polynomials in exponential inequalities, J. Symb. Comput. 13 (1992), 139–173.

28. A. Yao, Algebraic decision trees and Euler characteristics, in: Proc. IEEE Symp. on Foundations of Computer Science (1992), 268–277.

29. A. Yao, in: Proc. ACM Symp. on Theory of Computing (1994), 615–624, Decision tree complexity and Betti numbers, in: Proc. ACM Symp. on Theory of Computing (1994).

30. A. Yao, R. Rivest, On the polyhedral decision problem, SIAM J. Comput. 9 (1980), 343–347.