Lower Bounds on Testing Membership to a Polyhedron by

Algebraic Decision Trees

Dima Grigoriev^{∗}  Marek Karpinski^{†}  Nicolai Vorobjov^{‡}

Abstract

We describe a new method of proving lower bounds on the depth of algebraic decision trees and apply it to prove a lower bound Ω(log N) for testing membership to a convex polyhedron having N facets of all dimensions, provided that N is large enough. This bound apparently does not follow from the methods developed by M. Ben-Or, A. Björner, L. Lovasz, and A. Yao ([B 83], [BLY 92]) because the topological invariants used in these methods become trivial for a convex polyhedra.

Introduction

A problem of testing membership to a semialgebraic set Σ was considered by many authors (see, e.g., [B 83], [B 92], [BKL 92], [BL 92], [BLY 92], [MH 85], [Y 92], [Y 94], [YR 80] and the references there). Here we consider a problem of testing membership to a convex polyhedron P in n-dimensional space ℝ^{n}. Let P have N facets of all the dimensions. In [MH 85] it was shown, in particular, that for this problem O(log N)n^{O(1)} upper bound is valid for the depth of linear decision trees, in [YR 80] a lower bound Ω(log N) was obtained. A similar question was open for algebraic decision trees. In the present paper we prove a lower bound Ω(log N) for the depth of algebraic decision trees testing membership to P (see the theorem below).

Several topological methods were introduced for obtaining lower bounds for the complexity of testing membership to Σ by linear decision trees, algebraic decision trees , algebraic computation trees (the definitions one can find in, e.g., [B 83]).

∗Departments of Computer Science and Mathematics, Penn State University, University Park, PA 16802, Email:

dima@cse.psu.edu. Supported in part by the Volkswagen– Stiftung.

†Department of Computer Science, University of Bonn, 53117 Bonn, and the International Computer Science Institute, Berkeley, California. Research supported in part by DFG Grant KA 673/4–1, by the ESPRIT BR Grants 7097 and ECUS030, and by the Volkswagen-Stiftung. Email:

marek@cs.bonn.edu

‡Departments of Computer Science and Mathematics, Penn State University, University Park, PA 16802, Email:

vorobjov@theory.cse.psu.edu

In [B 83] a lower bound Ω(log C) was proved for the most powerful among the considered in this area computational models, namely algebraic computation trees, where C is the number of connected components of Σ or of the complement of Σ. After that, in [BLY 92], a lower bound Ω(log χ) for linear decision trees was proved , where χ is Euler characteristic of Σ, in [Y 92] this lower bound was extended to algebraic computation trees. A stronger lower bound Ω(log B) was proved later in [BL 92], [B 92] for linear decision trees, where B is the sum of Betti numbers of Σ (obviously, C, χ ≤ B). In the recent paper [Y 94] the latter lower bound was extended to the algebraic decision trees.

Unfortunately, all the mentioned topological tools fail when Σ is a convex polyhedron, because B = 1 in this situation. The same is true for the method developed in [BLY 92] for linear decision trees, based on the minimal number of convex polyhedra onto which Σ can be partitioned.

To handle the case of a convex polyhedron, we introduce in section 1 another approach based on a short description of a set of all sharp points of a semialgebraic set W which is accepted by a branch of an algebraic decision tree. Sharp points of W are its singular (nonsmooth) points of a special kind. In order to obtain such a description we use complexity bounds for quantifier elimination in the theory of real closed fields (see [GV 88], [G 88], [R 92], [HRS 90]).

In section 2 we give an upper bound for the number of facets of P which intersect by a full dimension with the set W (using lemma 3 from section 1 which states that these are exactly the facets having intersections of a full dimension with the subset of sharp points).

In section 3 we complete the proof of the theorem.

We conclude the paper discussing a much easier (than obtained in the theorem) lower bound Ω(log N_{0}), with N_{0} being the number of all (n−1)- dimensional facets, which is valid also for a more powerful model of algebraic computaion trees.

Now let us formulate precisely the main result.

We consider algebraic decision trees of a fixed degree d (see, e.g., [B 83], [Y 94]). Suppose that such a tree T, of the depth k, tests a membership to a convex polyhedron P ⊂ ℝ^{n}. Denote by N the number of facets of P of all dimensions from zero to n. In this paper we agree that a facet is “open”, i.e., does not contain facets of smaller dimensions.

Theorem.

k ≥ Ω(log N),

provided that N ≥ (dn)^{cn^{2}} for some c > 0.

Let us fix a branch of T which returns “yes”. Denote by f_{i} ∈ ℝ[X_{1}, …, X_{n}], 1 ≤ i ≤ k the polynomials of degrees deg(f_{i}) ≤ d, attached to the vertices of T along the fixed branch. Without loss of generality, we can assume that the corresponding signs of polynomials along the branch are

f_{1} = ⋯ = f_{k_{1}} = 0, f_{k_{1}+1} > 0, …, f_{k} > 0.

Then the (accepted) semialgebraic set

W = {f_{1} = ⋯ = f_{k_{1}} = 0, f_{k_{1}+1} > 0, …, f_{k} > 0}

lies in P. Our main technical problem is to give an upper bound for a number of facets Π of P such that dim(Π) = dim(Π ∩ W).

1 Sharp points

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 Π denote by \overline{Π} the dim(Π)-plane, containing Π.

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

dim(Q_{1}(0) ∩ Q_{2}(0)) =

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

Lemma 1. For each j with 1 ≤ j ≤ n there exists a family A_{j} 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.

Proof. It suffices to prove the lemma for i = n − j. One can find a proof in [C 85], but for convenience we give here an outline of another proof.

Let G_{j} be the Grassman variety of all i-subspaces in ℝ^{n}. Then G_{j} is irreducible projective variety and dim(G_{j}) = j(n − j) (see, e.g., [H 77]). For any Q ∈ G_{n−j} consider a projective subvariety H(Q) ⊂ G_{j} of all A ∈ G_{j} such that Q ∩ A ≠ {0}, then H(Q) has codimension 1 in G_{j}.

Assume  that  by

inductive hypothesis R_{1}, …, R_{l} ∈ G_{j} are chosen already for which

dim(H(R_{1}) ∩ ⋯ ∩ H(R_{l})) = j(n − j) − l,

with 0 ≤ l ≤ j(n − j). Let

H(R_{1}) ∩ ⋯ ∩ H(R_{l}) = ⋃_{ν} U_{ν}

be the the representation of the intersection as a union of irreducible components.

For every U_{ν} consider the subvariety

U_{ν} = {Q ∈ G_{n−j} : U_{ν} ⊂ H(Q)} ⊂ G_{n−j},

which is a proper subvariety because

⋂_{Q∈G_{n−j}} H(Q) = ∅.

Since G_{n−j} is irreducible, there exists Q ∈ G_{n−j} such that Q ∉ U_{ν} for every ν, which can be taken as R_{l+1} at the inductive step. Take A_{j} = {R_{1}, …, R_{j(n−j)+1}}.

Lemma 2. There exists a rotation of coordinates X_{1}, …, X_{n} such that after this rotation for every j, each R ∈ A_{j} and for every facet Π of P, the subspace R and the plane \overline{Π} become transversal.

Proof. Consider the algebraic variety R of all rotations of coordinates X_{1}, …, X_{n}. The nontransversality of a subspace R ∈ A_{j} to a facet Π imposes algebraic conditions (in the form of polynomial equations) on R.

These equations do not vanish simultaneously at every point of R. Indeed, fix an i-facet Π and a subspace R ∈ A_{j}. Due to lemma 1, there exists R′ ∈ A_{j} which is transversal to \overline{Π}. Choose a rotation which forces R′ to coincide with R.

It follows that for a fixed pair of i-facet and R ∈ A_{j} the subvariety of all rotations satisfying the equations has the dimension smaller than dim(R). Since the family of all facets is finite, almost all rotations from R satisfy the requirement of the lemma.

Below we suppose that the coordinate system meets the requirements of lemma 2.

Definition. For arbitrary i, 0 ≤ i ≤ n, a point x ∈ W is called i-sharp in W if there exists a real c < 1 such that for every real ε > 0, for every subset R ∈ A_{n−i} and for any two points x^{(1)}, x^{(2)} ∈ W ∩ R(x) the following holds: if

∥ x − x^{(1)} ∥=∥ x − x^{(2)} ∥= ε

then

∥ x^{(1)} − x^{(2)} ∥< 2εc.

Here ∥ · ∥ denotes the Euclidean norm in ℝ^{n}.

Denote the semialgebraic set of all i-sharp points by S_{i}.

Lemma 3. Let for a i-facet Π of P the set W ∩ Π contain a neighbourhood of some point x in Π. Then x is i-sharp.

Proof. Due to the supposed property of the rotation of the coordinate system (see lemma 2), for any R ∈ A_{n−i} the point x is a vertex (zero-facet) of the polyhedron P = P ∩ R(x). Fix R ∈ A_{n−i}. For every ε > 0 and each pair

x^{(1)}, x^{(2)} ∈ W ∩ R(x) such that

∥ x − x^{(1)} ∥=∥ x − x^{(2)} ∥= ε

the relation

∥ x^{(1)} − x^{(2)} ∥< 2ε

holds according to triangle inequality because x is a vertex of P. The existence of the required c for R in the definition follows from the existence of the maxima (less than π) among all possible flat angles in P with the vertex in x (taking into the account that the set of all such flat angles is compact). Then we take the maxima over all R ∈ A_{n−i}.

Lemma 4. dim(S_{i}) ≤ i.

Proof. Suppose that, contrary to our claim,

dim(S_{i}) = i_{1} ≥ i + 1.

Let a point x ∈ S_{i} have a smooth i_{1}-dimensional neighbourhood in S_{i} (in fact almost all the points of S_{i} are smooth) and denote by T_{x} the tangent i_{1}-plane to S_{i} at x.

Due to lemma 1, there exists R ∈ A_{n−i} such that T_{x} and R intersect transversaly, i.e., dim(T_{x} ∩ R(x)) = i_{1} − i.

By the implicit function theorem, for a neighbourhood σ of x in S_{i}, the intersection σ ∩ R(x) is smooth and its dimension is i_{1}−i (its tangent plane at x is T_{x} ∩ R(x)). Since the dimension i_{1} − i ≥ 1 this contradicts to i-sharpness of x, because by the definition of a smooth neighbourhood, for a sequence {ε_{r}} such that lim_{r→∞} ε_{r} = 0 there exist two sequences {x_{r}^{(1)}}, {x_{r}^{(2)}} ∈ σ ∩ R(x) such that for each sufficiently large r

∥ x − x_{r}^{(1)} ∥=∥ x − x_{r}^{(2)} ∥= ε_{r}

and

lim_{r→∞} \frac{∥ x_{r}^{(1)} − x_{r}^{(2)} ∥}{2ε_{r}} = 1.

2 Estimating the number of facets, containing sharp points

Lemma 5. For every i, 0 ≤ i ≤ n−1, the number ν_{i} of all i-facets Π of P such that dim(Π ∩ W) = i, does not exceed (kdn)^{O(n^{2})}.

Proof. First let us reduce the lemma to the case of compact P. Let t be the minimal dimension of facets of P and Π_{t} be a facet with dim(Π_{t}) = t. Then Π_{t} is a t-plane.

For each i-facet Π of P with dim(Π ∩ W) = i choose a point x_{Π} ∈ (Π ∩ W) such that a suitable neighbourhood of x_{Π} in Π is contained in W.

First consider the case t ≥ 1. Choose any hyperplane Σ transversal to Π_{t} such that the points x_{Π} for all i-facets Π lie in one of two semi-spaces of ℝ^{n} \ Σ, denote this semi-space by Σ̃. Replace P by (P ∩ Σ̃) ∪ Σ reducing t by one. Continue this process while t ≥ 1.

Now consider the case t = 0.

Observe that there exists a linear form L = β_{1}X_{1}+⋯+β_{n}X_{n} with β_{i} ∈ ℝ, 1 ≤ i ≤ n such that for every γ ∈ ℝ the intersection {L + γ ≥ 0} ∩ P is compact. Take γ such that x_{Π} ∈ P′ = {L + γ ≥ 0}∩P for all Π. The number of all i-facets Π′ of P′ such that dim(Π′ ∩W) = i is greater or equal to ν_{i}. From now on we assume, without loss of generality, that P is compact.

Following the definition, one can determine the set S_{i} of all i-sharp points by a formula Φ_{i} of firstorder theory of reals. Formula Φ_{i} involves quantifiers and free variables X_{1}, …, X_{n}.

We can assume that Φ_{i} is in a prenex form with the prefix of the following kind:

∃c∀ε∀X_{1}^{(1)} ⋯ ∀X_{n}^{(1)}∀X_{1}^{(2)} ⋯ ∀X_{n}^{(2)}.

The quantifier-free part of Φ_{i} is a Boolean combination of atomic subformulas of the kind h > 0 or h = 0 where h is a polynomial in variables

c, ε, X_{1}^{(1)}, …, X_{n}^{(1)}, X_{1}^{(2)}, …, X_{n}^{(2)}, X_{1}, …, X_{n} of a total degree at most max{2, d}. The number of atomic subformulas is less than O(kn^{2}) (see lemma 1 and the definition).

One can apply to Φ_{i} an algorithm for quantifier elimination in the theory of real closed fields (see [GV 88], [G 88], [HRS 90], [R 92]). The result would be an equivalent to Φ_{i} quantifier-free formula in a disjunctive normal form:

⋁_{1≤j≤J}(h^{(j)} = 0 & g_{1}^{(j)} > 0 & ⋯ & g_{I_{j}}^{(j)} > 0).

Here h^{(j)}, g_{1}^{(j)}, …, g_{I_{j}}^{(j)} ∈ ℝ[X_{1}, …, X_{n}]. Moreover, according to [R 92] (cf. also the estimates in [GV 88], [G 88], [HRS 90]) the following bounds hold:

I_{j} < (kdn)^{O(n)},
J < (kdn)^{O(n^{2})},  (1)

deg_{X_{1},...,X_{n}}(h^{(j)}), deg_{X_{1},...,X_{n}}(g_{s}^{(j)}) < (kdn)^{O(n)}.

Due to lemma 3, for an i-facet Π of P, the equality dim(Π ∩ W) = i is equivalent to dim(Π ∩ S_{i}) = i, so we can replace in the formulation of the lemma the former equality by the latter one. Moreover, taking into the account the inequality J < (kdn)^{O(n^{2})}, it is sufficient to prove the lemma separately for the conditions dim(Π ∩ S_{i}^{(j)}) = i for all 1 ≤ j ≤ J instead of dim(Π ∩ W) = i, where

S_{i}^{(j)} = {h^{(j)} = 0 & g_{1}^{(j)} > 0 & ⋯ & g_{I_{j}}^{(j)} > 0} ⊂ S_{i}.

Thus, we shall prove that the number ν_{i}^{(j)} of all i-facets Π of P such that dim(Π ∩ S_{i}^{(j)}) = i does not exceed (kdn)^{O(n^{2})}.

In case i = 0, the set S_{i} consists, due to lemma 4, of a finite number of points. Their number is less than (kdn)^{O(n^{2})} according to the estimates from [M 64], [T 65], taking into the account the bounds (1). In the remaining part of this proof we shall assume that i ≥ 1.

In the space ℝ^{n} one can introduce the Zariski topology (for its properties used below, see, e.g., [H 77]), in which each closed set coincides with a set of all zeros of a multivariate polynomial with real coefficients.

The Zariski topology on ℝ^{n} is Noetherian. In relation to it, the concepts of an irreducibility (over ℝ) of a set, and of the Krull dimension of a set are definable (note that for semialgebraic sets Krull dimension coincides with the Euclidean dimension). The theorem on the dimension of intersection is valid, which implies that for two closed irreducible subsets V_{1}, V_{2} ⊂ ℝ^{n}, either dim(V_{1} ∩ V_{2}) < min{dim(V_{1}), dim(V_{2})}, either V_{1} ⊂ V_{2} or V_{2} ⊂ V_{1}.

Each subset of ℝ^{n} can be (uniquely) represented as a finite union of its irreducible components. Let V be an irreducible component of S_{i}^{(j)} (by lemma 4, dim(V) ≤ i), and Π be an i-facet of P such that dim(Π ∩ V) = i. Applying the theorem on the dimension of intersection to the Zariski closure \overline{V} of V and to \overline{Π}, we conclude that \overline{V} ⊂ \overline{Π}, hence \overline{V} = \overline{Π}. Using this property, represent S_{i}^{(j)} as a union of its irreducible components:

S_{i}^{(j)} = ⋃_{1≤l≤r_{1}} V^{(l)} ∪ ⋃_{r_{1}+1≤l≤r} V^{(l)}  (2)

where for each l, 1 ≤ l ≤ r_{1}, there exists an i-facet Π of P such that V^{(l)} ⊂ Π and for each l, r_{1} + 1 ≤ l ≤ r, for every i-facet Π of P

dim(V^{(l)} ∩ Π) < i.

Consider an irreducible component V^{(l)}, 1 ≤ l ≤ r_{1} and the corresponding i-facet Π (such that dim(Π ∩ V^{(l)}) = i). Since V^{(l)} is closed in S_{i}^{(j)} and \overline{V^{(l)}} = \overline{Π}, we get that V^{(l)} ⊃ \overline{Π} ∩ S_{i}^{(j)}, hence V^{(l)} = \overline{Π}∩S_{i}^{(j)}. Because dim(Π∩S_{i}^{(j)}) = i, we conclude that h^{(j)} vanishes identically on \overline{Π}, therefore

V^{(l)} = \overline{Π} ∩ S_{i}^{(j)} = \overline{Π} ∩ \{g_{1}^{(j)} > 0 & ⋯ & g_{I_{j}}^{(j)} > 0\}. (3)

Introduce a polynomial

g = ∏_{1≤l≤I_{j}} g_{l}^{(j)},

and choose a real ε > 0 satisfying the following requirements:

(a) ε is smaller than the absolute value of any nonzero critical value of the restriction of g on \overline{Π} for any i-facet Π of P (by Sard’s theorem [Hi 76], there exist only a finite number of critical values);

(b) polynomial g−ε does not vanish identically on any irreducible component of every intersection V^{(l)}∩\overline{Π}, 1 ≤ l ≤ r (there exists at most finite number of possible values of ε such that g − ε vanishes identically on V^{(l)} ∩ \overline{Π}).

The property (a) implies (involving the implicit function theorem) that \overline{Π}∩\{g = ε\} is a nonsingular hypersurface in \overline{Π}.

From the property (b) it follows that

dim(\{g = ε\} ∩ V^{(l)} ∩ \overline{Π}) < i − 1  (4)

for each r_{1} + 1 ≤ l ≤ r.

Observe that, due to (a) and according to elementary facts from Morse theory [Hi 76], every connected component of the set V^{(l)} = \overline{Π} ∩ \{g_{1}^{(j)} > 0 & ⋯ & g_{I_{j}}^{(j)} > 0} (see (3)) contains at least one (necessarily compact) connected component of the hypersurface \{g = ε\} in \overline{Π} ^{1} (note that the signs of all polynomials g_{1}^{(j)}, …, g_{I_{j}}^{(j)} are constant on each connected component of {g = ε}). Thus, in order to estimate the number ν_{i}^{(j)} of all i-facets Π of P such that dim(Π∩S_{i}^{(j)}) = i, it is sufficient to bound properly the number of all connected components of \{g = ε\} in \overline{Π} ∩ \{g_{1}^{(j)} > 0 & ⋯ & g_{I_{j}}^{(j)} > 0\} for all i-facets Π.

The rest of the proof of the lemma closely follows [GKS 93].

Because of the property (a) of ε, for a fixed ifacet Π, each compact connected component G_{Π} of \overline{Π} ∩ \{g = ε\} divides \overline{Π} \ G_{Π} into exactly two connected components (according to Jordan-Brouwer theorem, see, e.g., [D 72]). Hence, the zero Betti number b_{0}(\overline{Π}\G_{Π}) = 2. Then, Alexander’s duality principle (see, e.g., [D 72]) implies that the (i−1)th Betti number,

b_{i−1}(G_{Π}) = b_{0}(\overline{Π} \ G_{Π}) − 1 = 1.

It follows that

ν_{i}^{(j)} ≤ ∑_{Π} ∑_{G_{Π}} b_{i−1}(G_{Π})

where the exterior sum ranges over all i-facets Π of P and the interior ranges over all connected components G_{Π} of \overline{Π}∩\{g = ε\}∩\{g_{1}^{(j)} > 0 & ⋯ & g_{I_{j}}^{(j)} > 0}.

Relations (2) and (3) imply:

S_{i}^{(j)} ∩ {g = ε} = (⋃_{Π} ⋃_{G_{Π}} G_{Π})∪

(⋃_{r_{1}+1≤l≤r} V^{(l)} ∩ {g = ε}) (5)

Here the union ∪_{Π} ranges over all i-facets Π of P.

Let us analyse the pairwise intersections of the sets involved in the union (5).

(i) For a fixed Π, any two different sets of the kind G_{Π} do not intersect being two different connected components.

(ii) For two different facets Π and Π′, two sets G_{Π} and G_{Π′} do not intersect. Indeed, G_{Π} and G_{Π′} lie in the Euclidean closures cl(Π), cl(Π′) of the facets Π, Π′ respectively. Suppose that there exists a point x ∈ G_{Π} ∩ cl(Π) ∩ cl(Π′), thus x ∈ cl(Π) \ Π. Then each point of a neighbourhood of x satisfies all the inequalities g_{l}^{(j)} > 0, 1 ≤ l ≤ I_{j}. Hence (because h^{(j)} vanishes identically on \overline{Π}),

S_{i}^{(j)} ∩ (\overline{Π} \ cl(Π)) ≠ ∅

which contradicts to S_{i}^{(j)} ⊂ P.

(iii) According to (4), for each i-facet Π of P the following holds:

dim(G_{Π} ∩ ( ⋃_{r_{1}+1≤l≤r} V^{(l)} ∩ {g = ε})) < i − 1.

Properties (i)—(iii) imply that (i − 1)-th Betti numbers of all pairwise intersections of the terms of the union (5) are zeroes. Therefore, applying Mayer–Vietoris theorem (see, e.g., [D 72]) to the union (5), we get:

b_{i−1}((⋃_{Π} ⋃_{G_{Π}} G_{Π}) ∪ ( ⋃_{r_{1}+1≤l≤r} V^{(l)} ∩ {g = ε})) ≥

1Actually there exists exactly one connected component of {g = ε} of this kind [GV 92], we do not use this fact here.

≥ ∑_{Π} ∑_{G_{Π}} b_{i−1}(G_{Π})+b_{i−1}( ⋃_{r_{1}+1≤l≤r} V^{(l)} ∩{g = ε}).

(6)

The right side of the inequality (6) is obviously not less than the first item

∑_{Π} ∑_{G_{Π}} b_{i−1}(G_{Π})

which is an upper bound for ν_{i}^{(j)} (see above).

On the other hand, the left side of (6), being (see (5)) equal to

b_{i−1}({h^{(j)} = 0 & g_{1}^{(j)} > 0 & ⋯ & g_{I_{j}}^{(j)} > 0 &

g = ε}),

does not exceed (kdn)^{O(n^{2})}, according to [M 64], [T 65] and taking into the account the bounds (1).

Hence the estimate ν_{i}^{(j)} < (kdn)^{O(n^{2})} is established. Since, by (1), J < (kdn)^{O(n^{2})}, we get:

ν_{i} ≤ ∑_{1≤j≤J} ν_{i}^{(j)} < (kdn)^{O(n^{2})}.

The lemma is proved.

3 The proof of the theorem

Now we are able to complete the proof of the theorem.

For each facet Π of P there exists at least one branch of the tree T with the output “yes” and having an accepted set W_{1} ⊂ ℝ^{n} such that

dim(W_{1} ∩ Π) = dim(Π).

Since there are at most 3^{k} different branches of T, the inequality

N < 3^{k}(kdn)^{O(n^{2})}  (7)

follows from lemma 5. Together, N ≥ (dn)^{Ω(n^{2})} (see the theorem in the introduction) and (7) imply

k ≥ Ω(log(N)).

The theorem is proved.

4 Algebraic computation trees

Consider now algebraic computation trees which constitute a more powerful computational model than algebraic decision trees (of a fixed degree) which we were dealing with so far (see, e.g., [B 83]).

Let an algebraic computation tree T_{0} of the depth k_{0} test a membership to an n-dimensional polyhedron P ⊂ ℝ^{n}. Denote by N_{0} the number of all (n − 1)-facets of P.

We claim that k_{0} ≥ Ω(log(N_{0})).

In order to prove that, consider any branch of T_{0} with the output “yes”. Let

W_{1} = {f_{1}^{(1)} = ⋯ = f_{k_{2}}^{(1)} = 0 &

f_{k_{2}+1}^{(1)} > 0 & ⋯ & f_{k_{0}}^{(1)} > 0} ⊂ P

be the semialgebraic (accepted) set, corresponding to this branch. In this formula f_{i}^{(1)} ∈ ℝ[X_{1}, …, X_{n}], 1 ≤ i ≤ k_{0} are all the polynomials occuring along the branch.

Obviously, deg(f_{i}^{(1)}) ≤ 2^{k_{0}} (cf. [B 83]).

Assume that for a (n−1)-facet Π of P, the dimension dim(W_{1} ∩ Π) = n − 1. Here, the (n − 1)-plane \overline{Π} is defined by

\overline{Π} = \{ ∑_{1≤j≤n} α_{j}X_{j} − β = 0\}

for some α_{j}, β ∈ ℝ.

Denote

f^{(1)} = ∑_{1≤i≤k_{2}}(f_{i}^{(1)})^{2}.

Evidently, f^{(1)} ≢ 0, otherwise the dimension of the open set W_{1}, dim(W_{1}) = n, which means that W_{1} ∩ (ℝ^{n} \ P) ≠ ∅.

Because polynomial f^{(1)} vanishes on \overline{Π}, the linear expression ∑ α_{j}X_{j} − β divides f^{(1)}, therefore the number of (n − 1)-facets such that dim(W_{1} ∩ Π) = n − 1 does not exceed

deg(f^{(1)}) < 2^{O(k_{0})}.

Since there are at most 3^{k_{0}} branches in T_{1}, arguing as at the end of the proof of the theorem, we get the lower bound

k_{0} ≥ Ω(log(N_{0})).

Note that the number of all facets of all dimensions N ≤ (max\{2, \frac{N_{0}}{n} \})^{n}, and this estimate is sharp. Thus, the bounds log(N) (from the theorem) and log(N_{0}) can differ by a factor O(n).

An interesting open problem is to prove the lower bound Ω(log(N)) for the depth of algebraic computation trees.

Acknowledgement

We thank Friedhelm Meyer auf der Heide for the number of interesting discussions.

References

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

[B 92] A. Björner, “Subspace arrangements,” Proceedings of 1st European Congress of Mathematicians, Paris, 1992.

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

[BLY 92] 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.

[BKL 92] P. Buergisser, M. Karpinski, and T. Lickteig “On randomized algebraic test complexity,” Technical Report TR-92-070, International Computer Science Institute, Berkeley, 1992; in J. of Complexity 9 (1993), pp. 231–251.

[C 85] A. Chistov “Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic,” Lecture Notes Computer Sci. 199, Springer–Verlag, 1985, 63–69.

[D 72] A. Dold “Lectures on Algebraic Topology,” Springer–Verlag, Berlin, 1972.

[G 88] D. Grigoriev “Complexity of deciding Tarski algebra” Journal Symbolic Comp. 5, 1988, 65–108.

[GK 93] D. Grigoriev, and M. Karpinski “Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Computation Trees,” Technical Report TR–93–042, International Computer Science Institute, Berkeley, 1993.

[GKS 93] D. Grigoriev, M. Karpinski, and M. Singer “Computational complexity of sparse real algebraic function interpolation,” Proceedings MEGA’92, in: Progress in Mathematics 109, Birkhäuser, 1993, 91–104.

[GV 88] D. Grigoriev, and N. Vorobjov “Solving systems of polynomial inequalities in subexponential time,” Journal Symbolic Comp. 5, 1988, 37–64.

[GV 92] D. Grigoriev, and N. Vorobjov “Counting connected components of a semialgebraic set in subexponential time,” Computational Complexity 2, 1992, 133–186.

[H 77] R. Hartshorn “Algebraic Geometry,” Springer–Verlag, 1977.

[Hi 76] M. Hirsch “Differential Topology,” Springer–Verlag, 1976.

[HRS 90] J. Heintz, M.-F. Roy, and P. Solernó “Sur la complexité du principe de Tarski-Seidenberg,” Bull. Soc. Math. France 118, 1990, 101–126.

[MH 85] F. Meyer auf der Heide “Fast algorithms for n-dimensional restrictions of hard problems,” Proceedings of ACM Symposium on Theory of Computing, 1985, 413–420.

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

[R 92] J. Renegar “On the computational complexity and the first order theory of the reals. Parts I–III,” Journal Symbolic Comp. 13, 1992, 255–352.

[T 65] R. Thom “Sur l’homologie des variétés algébriques réelles,” in: Differential and Algebraic Topology, S. S. Cairns, ed., Princeton University Press, 1965.

[Y 92] A. Yao “Algebraic decision trees and Euler characteristics,” Proceedings of IEEE Symposium on Foundations of Computer Science, 1992, 268–277.

[Y 94] A. Yao “Decision tree complexity and Betti numbers,” Proceedings of 26th ACM Symposium on Theory of Computing, 1994.

[YR 80] A. Yao, and R. Rivest “On the polyhedral decision problem,” SIAM J. Comput. 9, 1980, 343–347.