Please see PDF version
JOURNAL OF ALGORITHms 3, 1 8 (1982)
Lower Bounds for Algebraic Decision Trees
J. MICHAEL STEELE*
Department of Statistics, Stanford University, Stanford, California 94305
AND
ANDREW C. YA&
Computer Science Department, Stanford University, Stanford, California 94305
Received July 24, 1980; revised May 15, 1981
A topological method is given for obtaining lower bounds for the height of algebraic decision trees. The method is applied to the knapsack problem where an 2(n7) bound is obtained for trees with bounded degree polynomial tests, thus extending the Dobkin Lipton result for linear trees. Applications to the convex hull problem and the distinct element problem are also indicated. Some open problems are discussed.
1. INTRODUCTION
Decision trees are often used to model algorithms for combinatorial and geometrical problems. While motivation for these models rests primarily on their generality and conceptual simplicity, they also have the benefit of offering at present the most promising prospect for proving worst case lower bounds in many problems.
For linear decision trees several powerful techniques are known for bounding the tree height from below (e.g., Reingold [111, Dobkin [31, Dobkin and Lipton [4, 51, Yao [ 151, and Yao and Rivest [ 17]).
Much less is known for general algebraic decision trees. Beyond the naive information bound, Rabin's theorem (Rabin [101) and the convex hull problem (Yao [161) are apparently the only known results.
*The research of this author was supported in part by Office of Naval Research Contract N00014 76 C 0475 (NR 042 267).
tThe research of this author was supported in part by National Science Foundation Grant MCS 77 05313 A01.
0196 6774/82/010001 08$02.00/0 Copyright 0 1982 by Aeadernic Press, Inc.
All rights of reproduction in any forni reserved.
i
2 STEELE AND YAO
The purpose of this article is to provide a general method for establishing lower bounds for the worst case performance of algorithms prescribed by arbitrary algebraic decision trees. Technically this work extends the results of Dobkin and Lipton [4, 51, but the tools put to work here provide nontrivial bounds for a large class of previously untouchable problems.
Before giving the detailed computational model it seems worthwhile to mention informally a concrete application.
THEOREM 1. Any algebraic decision tree of bounded order which solves the n dimensional knapsack problem must have height at least 9(n 2).
This result extends the knapsack bounds under the linear decision tree model due to Dobkin and Lipton [41 and the 2(n log n) result of Dobkin [3].
The method used here rests critically on a result from real algebraic geometry due to Milnor [91. Since the machinery used by Milnor may not be familiar to workers in complexity, we have tried to give an exposition of the basic facts necessary for making this work self contained. The bounds discussed here should prove useful in many related problems.
In the next section we rigorously specify the computational model and outline the lower bound method. The third section exposits Milnor's inequality and gives a heuristic argument which tries to pinpoint the necessity for the more sophisticated tools.
The fourth section is devoted to applications and in particular to the proof of the result on the knapsack problem (Theorem 1) which was mentioned above.
The final section mentions some open problems and suggests a line of attack which if sufficiently developed might add significantly to the power of the present method.
2. COMPUTATIONAL MODEL AND THE GENERAL METHOD
Let W c a" be any set. A (dth order) decision tree T for testing if x EE W is a ternary tree with each internal node containing a test of the form P(Xl, X21 ... 1 Xn): 0, where p is a polynomial of degree at most d. Each leaf of T contains a "yes" or a "no" answer. For an input x, the procedure starts at the root and traverses down the tree. At each internal node a branching is made according to the polynomial test at that node and when a leaf is reached the answer to the question "Is x EE WT' must be given correctly.
Now let Cd(W) be the minimum height hT for any dth order decision tree T (for the set W). Our key objective will be to obtain lower bounds on Cd(W), and the bound given here will depend heavily on the topology of W.
By *W we denote the number of (disjoint) connected components of W. Also for any polynomial p(xl, X21 ... 1 X,) we set SP = {xl p(x) :71 0}, and
ALGEBRAIC DECISION TREES 3
for any integers n, m > 0 we put fl(m, n) = max{4SP 1 p is a polynomial of n real variables and of degree at most m}.
The following elementary result provides the skeleton of our method. (To put flesh on the bones will require the bounds on P obtained in the next section.)
THEOREM 2. Let W C: 6An be an open set, and let T be a dth order algebraic decision tree for deciding if x C W. If W is the disjoint union of N open sets, then the height h T satisfies the inequality
2 hp (hTd, n) ~> N.
Proof. For each leaf 1 of T let V, be the set of inputs x Ell R n leading to 1 and let I, be the set of constraints resulting from the tests. Let P be the set of leaves 1 such that I, consists only of strict inequalities and such that the answer stored at 1 is "yes." One should note that, for every 1 E1 C, V, is an open set and V, C W.
We now write W = U iN= 1 W, where each W, is a connected open set and the W, are disjoint, and write V, {x: ffl,(x) < 0,,~,,(x) < 0,..., ff,(x) < 0} where each & is a polynomial of degree not greater than d and where s:!~ hT. As a consequence of this representation, V, C: {xiq,(x) =i 4 0} = 6D, where ql(x) = II,~,.(x) is a polynomial of degree at most hTd. Moreover, each connected com'ponent of V, is contained in at most one component of 6D. Hence, V, has at most ft(hTd, n) connected components V111 V/21 ' .. '
Since each leaf of T is,correctly labeled, each V1j has to be completely contained in some Wi. Since the number of such VIj is at most fl(hTd, n) and there are only 1 P 1 values of 1 which lead to "yes," the number of components N of W is bounded by 1 C 1 ft(h.,d, n). In the last deduction, we have used the fact that each W, must contain some points in U 1 V, (since the set W U V, is of measure 0). Since 2hT ~ 1 C 1 the theorem follows. C]
3. COUNTING CONNECTED COMPONENTS
To use Theorem 2 one needs bounds on P(m, n) and this is apparently no easy matter. Fortunately, there is a bound due to Milnor [9, Theorem 31 which is sufficient for some applications:
T1 ft(m, n) :5 (m + 2)(m + 1)" '. (3.1)
The proof of Milnor's inequality rests on the several substantial results from Morse theory and algebraic topology, about which we will say more below. First we would like to give a heuristic indication of an analogous result.
The only preliminary needed for the argument is Bezout's theorem which
says that any system of n algebraic equations in n variables with degree d
4 STEELE AND YAO
has either infinitely many (complex) solutions or at most d". For a classical approach to the proof of Bezout's theorem one can consult Enriques [7], or, for the case n = 2, there is a nice proof in Seidenberg [ 121.
To use Bezout's theorem we suppose that p is a real polynomial in n variables with degree m, and we note that R can be chosen so that A = {x 1 x E: R% p (x) > 0, R' I"= 1 x' > 0} has at least as many bounded connected components as (x 1 p(x) > 0} has connected components (bounded or unbounded). Since each bounded connected component of A must contain a local maximum of pq, the number of bounded components of A is majorized by the number of zeros of the system V pq = 0. By Bezout's theorem, this number is either infinite, or else bounded by (m + 1)".
This finite bound is for our purposes almost as sharp as Milnor's bound. The real work comes in providing a rigorous perturbation argument which rules out the case when Bezout gives only the trivial infinite bound. That is precisely the case which causes all the trouble and presents this section from being self contained.
The inequalities proved in Milnor [9] actually provide bounds on the sum of the Betti numbers (in tech cohomology) for the set V = {xix E R% p(x) ~: 0}, where p is a polynomial of degree at most m. This leads immediately to the bound * V:5 L (m + 2)(m + 1)" 1, since the zeroth Betti number is 2
equal to the number of connected components (see Eilenberg and Steenrod [6, p. 254, Exercise A.31). The same bound remains true when V is defined by a strict inequality p(x) > 0; one can see this by utilizing the fact {xl p(x) > 0} = U,.OV, where V, = {xl p(x) k c}. This implies inequality (3.1).
For readers who are not familiar with the notions of Homology groups and Betti numbers, Chapter 6 of Hocking and Young [81 can provide a pleasant introduction. We should further remark that a recent exposition of Bott [21 gives a direct and intuitive introduction to Milnor [91 and the closely related ideas of Morse theory. As it happens, the problem of determining 8(m, n) is probably quite deep. As noted in Arnold [ 1 ], it is intimately connected with the basic concerns of Hilbert's 16th Problem.
Despite the apparent. simplicity of the heuristic argument given above, we benefit from a genuine stroke of good luck that any bound like (3. 1) is known.
4. APPLICATIONS
We now use Theorem 2 to derive lower bounds. Clearly, the function 2',8(xd, n) is an increasing function of x. Let a(d, n, N) be the minimum x satisfying 2x,8(xd, n) ~t N. Theorem 2 immediately yields the following
i
ALGEBRAIC DECISION TREES 5
formal bounds:
Cd(W) ~~ a(d, n,4 W). (4.1)
Any general upper bounds on 8 can be used to derive lower bounds on a and hence Cd. In particular, Milnor's bound (3. 1) gives the following result.
THEOREM 3. For any real E,
Cd (W) ~: min { E 1092 N, (M1 '01 1)
when N = *W
COROLLARY. If ""~ W= 2(n(' +8)n) for some fixed 8 > 0, then
Cd(W) 2(109CW)).
Proof Letx = Cd(W). Then 2,8(xd, n) ~t N. Hence by (3.1)
2x(xd + 1)n ~:> N.
Either 2x ~: N' or (xd + 1)" ~: N 1 ', proving the theorem. Cl
The corollary follows by writing #W = n nO +g(n)) and setting
1 g(n)
2 1 + g(n)
in the theorem.
Thus ' Theorem 3 gives a lower bound nonlinear in n when #W grows at least as fast as nO +8)n. This is also necessary since the theorem only gives a lower bound 0(n) when *W = 0(n"). n2/2;
In the first example given below, *W 2 thus we have a good lower bound. The other two examples have #W:5 n n , and Theorem 3 does not give nonlinear bounds. However, Theorem 2 (or, (4.1)) is still true for these later examples, and a better determination in the future may result in an improved bound.
ExAmPLE 1. THE KNAPSACK PROBLEM. Given real numbers XP X2....
x., decide if there exists some subset S C { 1, 2,. . n} such that 2, E Sxi =: 1 *
In this case, W = RX11 X21 ... 1 XJ1113(li,sxi 1) 7~: 0}. It was shown in Dobkin and Lipton [41 that *W ~: 2 n2/2. ThUS, Cd(W) = 2(n 2) for any fixed d. This generalizes the result of Dobkin and Lipton where they showed CI(W) = 2(n 2).
6 STEELE AND YAO
EXAMPLE 2. ELEMENT DISTINCTNESS. Given xl, X21 .... X, EE 6A, is there a pair i, j with i =,p~ j and xi = xj? In this case,
W= ((X11X21 1 Xn) (X, Xj) =,~~ 0 6An.
It is easily shown that *W = n! since each region ((XP X21 ... 1 Xn) 1 xa(l) < x~(2) < ... X0(,,)} is a maximal connected component of W for each permutation a. One therefore has Cd(W) = :t a(d, n, n!).
EXAMPLE 3. EXTREME POINTS. Given n points on the plane does the convex hull formed by them possess n vertices?
Here W cannot be expressed by an easy algebraic relation but it is still possible to show *W >. (n 1)L Obviously, W is an open set in (qL2)n . For any configuration (XP X21 ... 1 X0 in W C (a2)n, we have a cyclical ordering a of the points {xi 11 :5 i :5 n} which is given uniquely by taking the points in cyclical order. Clearly, any of the (n 1)! cyclical permutations can arise in this way so all that remains is to show that if a :76 a' then the configurations which give rise to these permutations are in disjoint components of W.
For each configuration in W we consider the (") element array A given by
3
A(XiXjXk), where A is the signed area of the triangle formed by the 3 set (XiXjX0 C {Xl, X21 ... 1 X0. If the configuration corresponding to a is continuously deformed in any way to the configuration for a' then A. is transformed continuously into A&. Since a and a' differ there is some triple (XiXjX0 for which A(XiXjXk) has differing signs in A,, and A... By the intermediate value theorem there is therefore some time during the continuous deformation when A(XiXjXk) = 0. This says that Xp Xj, Xk are then collinear and at that point there are at most n 1 extreme points in the configuration. This proves that any passage from a to a' must go out of W, so a and a' correspond to different components.
The main consequence of the preceding bound is that
Cd (W) k a (d, 2n, (n 1)!)
and it was originally hoped that this would be sufficient to prove a conjecture of Yao [16] that any algebraic decision tree of order d for the extreme point problem must have height 2(n log n). The Milnor bound in this case is not sufficiently sharp to obtain the desired bound. We indicate in the next section a bound which would be sufficient.
While these last two examples are disappointing in that they do not give the conjectured nonlinear lower bounds, one should note that since only a yes no answer is required there is a logical necessity of only two terminal
i
1
i
1
ALGEBRAIC DECISION TREES 7
leaves. So, the information theoretic bound in these two cases gives only the absurd bound 1092 2.
5. OPEN PROBLEMS AND DIRECTIONS
Surely the most interesting and important problems pivot about finding sharper bounds on fi(m, n). It is conceivable that #(m, n) = 20(m +n) which could imply by Theorem 2 that Cd(W) = S2(l/d(1092 N m)). This bound would yield an 2(n log n) lower bound in Examples 2 and 3 for fixed d.
In fact, a somewhat weaker result will suffice for this purpose. Let fl(d, m', n) be the maximum of 'S for any p of the form H it, pi p
(X,, X21 ... XJ, with each pi of degree not greater than d. Clearly #(d, m', n) :5,8(dm', n). The result one really needs in Examples 2 and 3 is fi(d, m', n) = 2'('m"n). Can one prove better bounds on #(d, m', n) than on #(m, n)? Here we note that it is not hard to see that
n
#(I, M" n) :5 jy= 0 n :5 m', (5.1)
since #(I, m', n) just equals the number of regions of W which can be partitioned by m' hyperplanes. (This is proved in Steiner (1926) 1131, which is in the first volume of Crelle's J. Reine Angew. Math. and which is better remembered for containing five fundamental papers of N. H. Abel. For modern treatment of (5. 1) see Wetzel [ 141 and the references given there.)
A more modest approach to the problems suggested by Examples 2 and 3 rests on obtaining bounds for any small values of d k 2. It is known (Yao [ 161) that C2(W) = 2(n log n) in Example 3, but there are no other known nonlinear lower bounds even in the case d = 3.
ACKNOWLEDGMENT
We wish to thank Maria Klawe for her help in interpreting Milnor's result.
REFERENCES
1. V. ARNOLD, Real algebraic geometry (The 16th Hilbert problem), Proc. Symp. Pure Math. 28 (Part 1) (1976), 50 51.
2. R. BoTT, "Some Recollections from 30 Years Ago," in "Constructive Approaches to Mathematical Models" (C. V. CofTman and G. J. Fix, Eds.) Academic Press, New York, 1979.
3. D. DoBKIN, A nonlinear lower bound on linear search tree programs for solving knapsack problems, J. Comput. Syste,m Sci. 13 (1976), 69 73.
i
8 STEELE AND YAO
4. D. DOBKIN AND R. J. LiPTON, A lower bound of 1 J
2 on linear search programs for the
knapsack problem, J. Compui. System Sci. 16 (1978), 413 417.
5. D. DOBKIN AND R. J. LIPTON, On the complexity of varying sets of primitives, J. Comput.
System Sci. 18 (1980), 86 9 1.
6. S. EILENBERG AND N. STEENROD, "Foundations of Algebraic Topology," Princeton Univ.
Press, Princeton, NI, 1952.
7. F. ENRIQUES, "Lezioiii Sulla Teoria Geometrica delle Equazioni e delle Funzioni Alge
braiche, " Vol. 2, pp. 10 1 104, Nicola Zanichelli, Bologna, 1915.
8. J. G. HOCKING AND G. S. YOUNG, "Topology," Addison Wesley, Reading, Mass., 1961.
9. J. MILNOR, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964),
275 280.
10. M. RABIN, Proving the simultaneous positivity of linear forms, J. Comput. System Sci. 13
(1972), 639 650.
11. E. REINGOLD, Computing the maximum and the median, in "Proceedings, Twelfth Annual
Symposium on Switching and Automata Theory, 197 1," pp. 216 218.
12. A. SEIDENBERG, "Elements of the Theory of Algebraic Curves," p. 44, Addison Wesley, Menlo Park, Calif. 1968.
13. J. STEINER, Eir iige Gesetze fiber die Theilung der Ebene und des Raumes, J. Reine Angew
Math. (1826), 349 364.
14. J. E. WETZEL, On the division of the plane by lines, Amer. Math. Monthly 85 (1978),
647 655~
15. A. C. YAO, On the complexity of comparison problems using linear functions, in "Proceedings, Sixteenths Annual Symposium on the Foundations of Computer Science, Berkeley, 1975," pp. 85 89.
16. A. C. YAO, "A Lower Bound to Finding Convex Hulls," Stanford Computer Science
Report STAN CS 79 733, April 1979 (J. Assoc. Comput. Mach., in press).
17. A. C. YAO AND R. L. RiVEST, On the polyhedral decision problem, SIAM J. Comput. 9
(1980), 343 347.
1
1
1