Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates

(Extended abstract)

Dima Grigoriev^{∗}  Nicolai Vorobjov

Departments of Computer Science and Mathematics

Penn State University University Park, PA 16802

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. This method differs essentially from the approaches adopted for algebraic computation trees ([1], [4], [26], [13]).

1 Pfaffian computation trees

We consider the following computation model, a generalization of the algebraic computation trees (see, e.g., [1], [26]).

Definition 1. Pfaffian computation tree T is a tree at every node v of which a Pfaffian function f_{v} in variables X_{1}, …, X_{n} is attached, which satisfies the following properties. Let f_{v_{0}}, …, f_{v_{l}}, f_{v_{l+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_{l+1} = v. We assume that the Pfaffian function f_{v} satisfies the following differential equation (see [20]):

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

where g_{v,j} are polynomials with real coefficients.

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 assign (by induction on the depth l + 1 of v) a set U_{v} ⊂ R^{n} consisting of all the points for which the sign conditions for the functions f_{v_{0}}, …, f_{v_{l}} along the branch T_{v} are valid. Thus, at the induction step, one assigns to three sons of v the sets

U_{v} ∩ {f_{v} > 0}, U_{v} ∩ {f_{v} = 0}, U_{v} ∩ {f_{v} < 0},

respectively. We assume also that the function f_{v} is real analytic in U_{v}. To each leaf w of T an output “yes” or “no” is assigned, we call the set U_{w} accepting set if to w “yes” is assigned. We say that T tests the membership problem to the union of all accepting sets (sf. [1]).

Taking polynomials as the gate functions f_{v} in T , we come to the algebraic computation trees. The examples of other gate Pfaffian functions f_{v} for 0 ≤ q ≤ l are:

(1) exp(f_{v_{q}});

(2) 1/f_{v_{q}}, defined for f_{v_{q}} ≠ 0;

(3) log(f_{v_{q}}), with log defined on the positive halfline;

(4) sin(f_{v_{q}}), with sin defined on an interval (−π + 2πr, π + 2πr);

(5) tan(f_{v_{q}}), with tan defined on (−π/2 + πr, π/2 + πr);

(6) \sqrt{f_{v_{q}}}, with square root defined on the positive half-line.

We suppose that the degrees deg(g_{v,j}) of the polynomials occuring in the definition of the gate functions f_{v} in T , are less than d.

Now let us formulate the main result.

Theorem. Let a Pfaffian computation tree T test the membership problem to a closed convex polyhedron P ⊂ R^{n}, having N facets of all dimensions from zero to n. Then the depth k of T is greater than Ω(\sqrt{log N}), provided that N ≥ (nd)^{Ω(n^{4} log d)}.

∗Supported in part by Volkswagen-Stiftung

The complete proof of the theorem one can find in [16]. Here we outline some of its ideas.

A special case of the theorem, when n = 2, so P is a polygon, was proved in [12].

Several methods, based on topological characteristics, are known for obtaining complexity lower bounds for algebraic computation trees testing membership to a semialgebraic set S ⊂ R^{n}. In [1] the bound Ω(log C) was proved, where C is the number of connected components of S or of its complement, in [2], [4], [25] the bound Ω(log χ) for Euler characteristic χ of S was obtained. A stronger lower bound Ω(log B) was proved in [2], [3], [26], where B is the sum of Betti numbers of S. Actually, one can directly extend these results to Pfaffian computation trees, replacing in the proofs the references to Milnor’s bound [22] for B by the references to Khovanskii’s bound [19], [20] for the sum of Betti numbers of a semi-Pfaffian set.

This leads to the following proposition [12].

Proposition. If a Pfaffian computation tree tests the membership problem to a semi-Pfaffian set with the sum of Betti numbers B, then the depth of the tree is greater than Ω(\sqrt{log B}).

There is a conjecture that the bound in [20] can be improved. If this were true, it would lead to the bound Ω(log N) in the theorem and Ω(log B) in the proposition.

Observe that because the sum of Betti numbers of a convex polyhedron is 1, the theorem does not, apparently, follow from the proposition. In [13] the bound Ω(log N) was proved for testing membership to a polyhedron with N facets by an algebraic decision tree (for N large enough, cf. the theorem). In [27] a similar lower bound was shown for a weaker model of linear decision trees. One cannot directly extend the method from [13] to Pfaffian computation trees since in [13] the effective quantifier elimination procedure for the first-order theory of reals (see [15], [10], [17], [23]) was essentially used, while for the theories involving Pfaffian functions (for instance, exp), the quantifier elimination does not exist [7], [8].

The computations involving other functions, besides arithmetic, were considered in several papers. In [18] for the circuits involving root extractions a complexity lower bound for computing an algebraic function was obtained, in [14] this result was extended to the circuits involving exp and log. In [11] lower bounds on parallel complexity for Pfaffian sigmoids were obtained.

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

2 Nonstandard fields and angle points

Fix an accepting set U_{w} ⊂ P and let v_{0}, v_{1}, …, v_{k} = w be all the nodes of the branch in T leading from the root to w. Then U_{w} = {f_{v_{0}}σ_{0}0, f_{v_{1}}σ_{1}0, …, f_{v_{k}}σ_{k}0} for suitable signs σ_{0}, …, σ_{k} ∈ {<, =, >}. Rename the functions ±f_{v_{0}}, …, ±f_{v_{k}} by u_{0}, …, u_{k} in such a way that U_{w} = {u_{0} = ⋯ = u_{k_{1}} = 0, u_{k_{1}+1} > 0, …, u_{k} > 0}. Denote f = u_{0}^{2} + ⋯ + u_{k_{1}}^{2}.

Because for each i-dimensional facet P_{i} of P there exists an accepting set U_{w_{1}} such that dim(U_{w_{1}} ∩P_{i}) = i, for proving the theorem it is sufficient to bound from above the number ν_{i} of i-dimensional facets P_{i} for which dim(U_{w} ∩ P_{i}) = i.

Estimation of ν_{i} uses essentially the notion of iangle points. In order to define this notion, we have to invoke nonstandard extensions of reals, which we now briefly describe following [24]. The details could be found in [6]. The nonstandard extensions were used in [24], their algebraic version was essentially involved in [15], [10], [17], [23] for effective solving systems of inequalities and deciding Tarski algebra.

There exists a sequence of ordered fields

R_{0} = R ⊂ R_{1} ⊂ R_{2} ⊂ ⋯ ⊂ R_{j} ⊂ ⋯

in which the field R_{j}, j ≥ 1 contains an element ε_{j} > 0 infinitesimal relative to the elements of R_{j−1} (i.e., for every positive element a ∈ R_{j−1} the inequality ε_{j} < a is true). In addition, for every function

φ : R_{j−1}^{n} ⟶ R_{j−1}

there exists a natural extension of φ which is a function from R_{j}^{n} to R_{j}. We say that R_{i} is a nonstandard extension of R_{j} for 0 ≤ j < i.

Consider the language L_{j}, j ≥ 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 R_{j} taking values in R_{j}, and the only predicate is the equality relation. We shall say that a closed (i.e., containing no free variables) formula Φ of the language L_{j} is true in R_{j}, j ≥ 0, if and only if the statement expressed by this formula with respect to R_{j} is true. The following “transfer principle” is valid: for all integers 0 ≤ j < i the closed formula Φ of L_{j} is true in R_{j} if and only if it is true in R_{i}.

An element z ∈ R_{i}, i ≥ 0 is called infinitesimal relative to R_{j}, 0 ≤ j < i if for every 0 < w ∈ R_{j} the inequality |z| < w is valid. An element z ∈ R_{i} is called infinitely large, if z = 1/z_{0}, where z_{0} is infinitesimal. If z ∈ R_{i} not infinitely large relative to R_{j}, z is called R_{j}-finite.

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

Denote m = n^{3} − n^{2} + n and standard part st_{m} we denote for brevity by st.

Definition 2. A point x ∈ U_{w} ⊂ R_{m+2}^{n} is called 0-quasiangle if the inequalities

u_{k_{1}+1}(x) ≥ ε_{1}, …, u_{k}(x) ≥ ε_{1}

are valid, there exist the points y_{1}, …, y_{n} ∈ {f = ε_{m+2}} such that the distances ∥y_{i} − x∥ ≤ ε_{m+1}, 1 ≤ i ≤ n and

det |\frac{grad_{y_{1}}(f)}{∥grad_{y_{1}}(f)∥}, …, \frac{grad_{y_{n}}(f)}{∥grad_{y_{n}}(f)∥}| > ε_{1},

where grad_{y}(f) = (\frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{n}} )^{T} (y).

One can prove with the help of the transfer principle that ε_{m+2} is not a critical value of f, hence grad_{y_{j}}(f) ≠ 0, 1 ≤ j ≤ n.

A semi-Pfaffian set (see, e.g., [8], [9]) is defined, roughly speaking, as a set of points in R^{n} satisfying a Boolean formula with the atomic subformulas of the form (g > 0), where g is a Pfaffian function.

A sub-Pfaffian set is defined as a set of points in R^{n} satisfying a formula (called Pfaffian formula over R) with quantifiers ∀, ∃ restricted to bounded intervals, where the quantifier-free part is a Boolean formula with the atomic subformulas of the form (g > 0).

A sub-Pfaffian set has a finite number of connected components each being, in its turn, a sub-Pfaffian set [8]. On the other hand, a theorem of Gabrielov [7], [8] states that each sub-Pfaffian set can be represented by a formula with solely existential quantifiers (unfortunately the bounds for resulting formula are not efficient).

In [19], [20] an explicit efficient bound is proved on the number of all connected components of a semi-Pfaffian set. This obviously implies the same bound on the number of the connected components for a sub-Pfaffian set given by a formula with solely existential quantifiers, because a projection of a connected set is connected.

One can extend the definitions of semi-Pfaffian and sub-Pfaffian sets to nonstandard fields. If a sub-Pfaffian set is defined by a Pfaffian formula over a field R_{j}, then the same formula defines a sub-Pfaffian set over a field R_{i}, i ≥ j; we call the latter set the completion of the former one, and use for it the same notation.

The bound for the number of all connected components of a sub-Pfaffian set (in particular, finiteness of this number) holds also over nonstandard fields due to the transfer principle and the theorem of Gabrielov.

Note that U_{w} is semi-Pfaffian, while the set of all 0-quasiangle points is sub-Pfaffian.

In [5] (see also [13])it was proved that for each 1 ≤ j ≤ n there exists a family A_{j} consisting of j(n−j)+1 j-dimensional subspaces in R^{n} such that for any (n − j)-dimensional subspace Q ⊂ R^{n} there is a certain element R ∈ A_{j} for which (R ∩ Q) = {0}.

Definition 3. A point x ∈ U_{w} is called i-quasiangle (0 ≤ i < n) if for each subspace Π ∈ A_{n−i} the point x is a 0-quasiangle point in the semi-Pfaffian set U_{w} ∩ Π(x) where Π(x) is the (n − i)-dimensional plane parallel to Π and passing through x (here we apply the Definition 2 of 0-quasiangle points to the restriction of f on Π(x)).

The set of all i-quasiangle points we denote by Ã_{i} ⊂ U_{w}. Observe that Ã_{i} is sub-Pfaffian.

Definition 4. The points of the set A_{i} = st(Ã_{i}) ⊂ R_{m}^{n} are called i-angle.

Lemma 1. The set A_{i} is sub-Pfaffian and A_{i} ⊂ U_{w}.

The next lemma shows, informally speaking, that if for i-dimensional facet P_{i} of P we have dim(U_{w}∩P_{i}) = i (recall that our purpose is to estimate the number ν_{i} of such P_{i}), then U_{w} ∩ P_{i} lies both in Ã_{i} and in A_{i}.

Lemma 2. Assume that dim(U_{w}∩P_{i}) = i. If for two points x̃ ∈ U_{w} ∩ P_{i} ∩ R^{n}, x ∈ P_{i} ∩ R_{m}^{n} the distance ∥x̃ − x∥ is infinitesimal relative to R then x ∈ Ã_{i} and x ∈ A_{i}.

Lemma 3. dim(A_{i}) ≤ i.

Lemmas 2 and 3 allow to reduce the estimating of ν_{i} to the problem of estimating the number of i-dimensional facets P_{i} of P which have full idimensional intersections with at most i-dimensional set A_{i}. This problem is treated in the next section.

3 Flat points

Definition 5. Let 0 ≤ i ≤ n − 1. A point x ∈ A_{i} is called 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 all i-flat points. Note that for i = 0 Lemma 3 entails that dim(A_{0}) ≤ 0, i.e. A_{0} consists of at most a finite number of points, therefore Φ_{0} = A_{0}.

Lemma 4. There is at most a finite number of iplanes Π for which dim(Π ∩ Φ_{i}) = i, and Φ_{i} is contained in the union of all such i-planes.

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

Lemma 5 allows to reduce the problem under consideration, of estimating the number of P_{i} such that dim(A_{i} ∩ P_{i}) = i, to estimating the number of all connected components of Φ_{i}. Because we are able (see Section 2) to bound the number of all connected components of a sub-Pfaffian set given by a Pfaffian formula with solely existential quantifiers (this is not the case for the sub-Pfaffian set Φ_{i}), we introduce the following notion.

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}

and the points

y + ∑_{1≤l≤i} ε_{ji+l+1}(v_{l} − y) ∈ Ã_{i}

for all 0 ≤ j ≤ n^{2}.

Denote the sub-Pfaffian set of all i-pseudoflat points by Φ̃_{i}. Observe that Φ̃_{i} can be defined by a Pfaffian formula with solely existential quantifiers.

The following lemma justifies the introduction of infinitesimals ε_{ji+l+1} in Definition 6.

Lemma 6. Let the points x, v_{1}, …, v_{i} ∈ A_{i} be such that the vectors v_{1} −x, …, v_{i} −x are linearly independent. Denote by Π the unique i-plane passing through x, v_{1}, …, v_{i}. If the points

x + ∑_{1≤l≤i} ε_{ji+l+1}(v_{l} − x) ∈ A_{i}

for all 0 ≤ j ≤ n^{2}, then dim(A_{i} ∩ Π) = i.

The proof of the next inclusion relies on Lemma 6.

Lemma 7. st(Φ̃_{i}) ⊂ Φ_{i}.

Using Lemma 2 we obtain the following lemma.

Lemma 8. If dim(U_{w} ∩ P_{i}) = i then U_{w} ∩ P_{i} ∩ R^{n} ⊂ Φ̃_{i}.

One can prove (cf. Lemma 1 in [15]) that for any connected sub-Pfaffian set V its standard part st(V) is also connected. Together with Lemmas 7, 8 this allows to reduce the estimating the number of all connected components ϕ of Φ_{i} such that dim(ϕ ∩ P_{i}) = i for some i-facet P_{i} of P (see Lemma 5), to estimating the number of connected components of Φ̃_{i}. The latter follows from Khovanskii’s bound [19], [20].

Lemma 9. The number of all connected components of the set Φ̃_{i} does not exceed 2^{k^{2}}(ndk)^{O(k+n^{4})}.

We conclude that ν_{i} ≤ 2^{k^{2}}(ndk)^{O(k+n^{4})}. Hence, N < 3^{k}2^{k^{2}}(ndk)^{O(k+n^{4})} (see the beginning of Section 2). This implies the theorem.

References

[1] M. Ben-Or, Lower bounds for algebraic computation trees, Proceedings of ACM Symposium on Theory of Computing, 1983, 80-86.

[2] A. Björner, Subspace arrangements, Proceedings of 1st European Congress of Mathematicians, Paris, 1992.

[3] A. Björner, and L. Lovasz, Linear decision trees, subspace arrangements and Möbius functions, Preprint, 1992.

[4] A. Björner, L. Lovasz, and A. Yao, Linear decision trees: volume estimates and topological bounds, Proceedings of ACM Symposium on Theory of Computing,1992, 170-177.

[5] A. Chistov, Fast parallel calculation of the rank of matrices over a field of arbitrary characteristics, Lecture Notes in Computer Science, V. 199, 1985, 63-69.

[6] M. Davis, Applied Nonstandard Analysis, John Wiley, 1977.

[7] A. Gabrielov, Projections of semi-analytic sets, Functional Anal. Appl., V. 2, 1968, 282-291.

[8] A. Gabrielov, Existential formulas for analytic functions, Preprint 93-60, Math. Sciences Inst., Cornell University, 1993.

[9] A. Gabrielov, and N. Vorobjov, Complexity of stratifications of semi-Pfaffian sets, Preprint 94-4, Math. Sciences Inst., Cornell University, 1994.

[10] D. Grigoriev, Complexity of deciding Tarski algebra, Journal Symbolic Comp., V. 5, 1988, 65-108.

[11] D. Grigoriev, Deviation theorems for Pfaffian sigmoids, St. Petersburg Math. Journal, V. 6, 1994, 127-131.

[12] D. Grigoriev, and M. Karpinski, Lower bounds on complexity of testing membership to a polygon for algebraic, randomized and exp − log trees, Technical report TR-93-042, International Computer Science Institute, Berkeley, 1993.

[13] D. Grigoriev, M. Karpinski, and N. Vorobjov, Lower bounds on testing membership to a polyhedron by algebraic decision trees, Proceedings of ACM Symposium on Theory of Computing, 1994, 635-644.

[14] D. Grigoriev, M. Singer, and A. Yao, On computing algebraic functions using logarithms and exponentials, Technical report 93-07, DIMACS, 1993.

[15] D. Grigoriev, and N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, Journal Symbolic Comp., V. 5, 1988, 37-64.

[16] D. Grigoriev, and N. Vorobjov, Complexity lower bounds for computation trees with elementary transcendental function gates, Preprint, 1994.

[17] J. Heintz, M.-F. Roy, and P. Solernó, Sur la complexite du principe de Tarski-Seidenberg, Bull. Soc. Math. France, V. 118, 1990, 101-126.

[18] J. Já Já, Computation of algebraic functions with root extractions, Proceedings of IEEE Symposium on Foundations of Computer Science, 1981, 95-100.

[19] A. Khovanskii, Fewnomials and Pfaff manifolds, Proceedings of International Congress of Mathematicians, Warszawa, 1983, 549-564.

[20] A. Khovanskii, Fewnomials, Translations of Mathematical Monographs, V. 88, Amer. Math. Soc., 1991.

[21] F. Meyer auf der Heide, Fast algorithms for ndimensional restrictions of hard problems, Proceedings of ACM Symposium on Theory of Computing, 1985, 413-420.

[22] J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc., V. 15, 1964, 275-280.

[23] J. Renegar, On the computational complexity and the first order theory of the reals. Parts I-III, Journal Symbolic Comp., V. 13, 1992, 255-352.

[24] N. Vorobjov, The complexity of deciding consistency of systems of polynomial in exponential inequalities, Journal Symbolic Comp., V. 13, 1992, 139-173.

[25] A. Yao, Algebraic decision trees and Euler characteristics, Proceedings of IEEE Symposium on Foundations of Computer Science, 1992, 268-277.

[26] A. Yao, Decision tree complexity and Betti numbers, Proceedings of ACM Symposium on Theory of Computing, 1994, 615-624.

[27] A. Yao, and R. Rivest, On the polyhedral decision problem, SIAM J. Comput., V. 9, 1980, 343-347.