A lower bound for randomized algebraic decision trees
Tóm tắt
We prove the firstnontrivial (andsuperlinear) lower bounds on the depth ofrandomized algebraic decision trees (with two-sided error) for problems being finite unions of hyperplanes and intersections of halfspaces, solving a long standing open problem. As an application, among other things, we derive, for the first time, an Ω(n
2)randomized lower bound for theKnapsack Problem, and an Ω(n logn)randomized lower bound for theElement Distinctness Problem which were previously known only for deterministic algebraic decision trees. It is worth noting that for the languages being finite unions of hyperplanes our proof method yields also a new elementary lower bound technique for deterministic algebraic decision trees without making use of Milnor's bound on Betti number of algebraic varieties.
Tài liệu tham khảo
M. Ben-Or,Lower Bounds for Algebraic Computation Trees, Proc. 15th ACM STOC (1983), pp. 80–86.
C.H. Bennett andJ. Gill,Relative to a Random Oracle A, P A ≠ NP A ≠ co-NP A with Probability 1, SIAM J. Comput.10 (1981), pp. 96–113.
A. Björner, L. Lovász and A. Yao,Linear Decision Trees: Volume Estimates and Topological Bounds, Proc. 24th ACM STOC (1992), pp. 170–177.
P. Bürgisser, M. Karpinski andT. Lickteig,On Randomized Algebraic Test Complexity. J. of Complexity9 (1993), pp. 231–251.
D.P. Dobkin andR.J. Lipton,A Lower Bound of 1/2n 2 on Linear Search Programms for the Knapsack Problem, J. Compt. Syst. Sci.16 (1978), pp. 413–417.
H. Edelsbrunner,Algorithms in Computational Geometry, Springer, 1987.
D. Grigoriev andM. 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.
D. Grigoriev and M. Karpinski,Lower Bound for Randomized Linear Decision Tree Recognizing a Union of Hyperplanes in a Generic Position, Research Report No. 85114-CS, University of Bonn, 1994.
D. Grigoriev, M. Karpinski, F. Meyer Auf Der Heide and R. Smolensky,A Lower Bound for Randomized Algebraic Decision Trees, Proc. ACM STOC (1996), pp. 612–619.
D. Grigoriev, M. Karpinski andN. Vorobjov,Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees, Discrete Comput. Geom. 17 (1997), pp. 191–215.
D. Grigoriev andN. Vorobjov,Solving Systems of Polynomial Inequalities in Subexponential Time, Journal of Symbolic Comp.5 (1988), pp. 37–64.
S. Lang,Algebra, Addison-Wesley, New York, 1984.
P. McMullen andG. Shephard,Convex Polytopes and the Upper Bound Conjecture, Cambridge University Press, Cambridge (1971).
S. Meiser,Point Location in Arrangements of Hyperplanes, Information and Computation106 (1993), pp. 286–303.
F. Meyer Auf Der Heide,A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem, J. ACM31 (1984), pp. 668–676.
F. Meyer auf der Heide,Nondeterministic versus Probabilistic Linear Search Algorithms, Proc. IEEE FOCS (1985a), pp. 65–73.
F. Meyer auf der Heide,Lower Bounds for Solving Linear Diophantic Equations on Random Access Machines, J. ACM32 (1985b), pp. 929–937.
F. Meyer auf der Heide,Simulating Probabilistic by Deterministic Algebraic Computation Trees, Theoretical Computer Science41 (1985c), pp. 325–330.
U. Manber andM. Tompa,Probabilistic, Nondeterministic and Alternating Decision Trees, J. ACM, Vol. 32 (1985), pp. 720–732.
M. Snir,Lower Bounds for Probabilistic Linear Decision Trees, Theor. Comput. Sci., Vol. 38 (1985), pp. 69–82.
J. M. Steele andA. C. Yao,Lower Bounds for Algebraic Decision Trees, J. of Algorithms3 (1982), pp. 1–8.
A. Tarski,A Decision Method for Elementary Algebra and Geometry, University of California Press, 1951.
A. Yao,A Lower Bound to Finding Convex Hulls, J. ACM28 (1981), pp. 780–787.
A. Yao,Algebraic Decision Trees and Euler Characteristics, Proc. 33rd IEEE FOCS (1992), pp. 268–277.
A. Yao,Decision Tree Complexity and Betti Numbers, Proc. 26th ACM STOC (1994), pp. 615–624.