Abstract
We prove general lower bounds for set recognition on random access machines (RAMs) that operate on real numbers with algebraic operations {+, −, ×, /}, as well as RAMs that use the operations {+, −, ×, ⌈ ⌋}. We do it by extending a technique formerly used with respect to algebraic computation trees. In the case of algebraic computation trees, the complexity was related to the number of connected components of the set W to be recognized. For RAMs, two similar results apply to the number of connected components of Wo, the topological interior of W. Other results use (¯W)o, the interior of the topological closure of W.
We present theorems that can be applied to a variety of problems and obtain lower bounds, many of them tight, for the following models:
-
1.
A RAM which operates on real numbers, using integers to address memory, and either the operations {+, −, ×, /} or {+, −, ×, ⌈ ⌋};
-
2.
A RAM of each of the above instruction sets, extended by allowing arbitrary real numbers to be used as memory addresses, and adding a test-for-integer instruction.
-
3.
A RAM of each of the above instruction sets which can compute with arbitrary real numbers, as well as use them for memory addressing, while having the provision that the input is always integer (for one result on this model, we require that all program constants be rational).
Part of this research was performed while this author was a PhD student at Tel-Aviv University.
Partially supported by NSF grant CCR-93-16209 and CISE Institutional Infrastructure Grant CDA-90-24735.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Ben-Or, “Lower bounds on algebraic computation trees,” Proc. Fifteenth Annual ACM Symp. on Theory of Computing (1983), 80–86.
N. H. Bshouty, “Lower bounds for the complexity of functions in a realistic RAM model,” Proc. Israel Symposium on the Theory of Computing and Systems, Haifa, 1992.
N. H. Bshouty, Y. Mansour, B. Schieber and P. Tiwari, “Fast exponentiation with the floor operation,” Computational Complexity 2 (1992), 244–255.
E. Dittert and M. J. O'Donnell, “Lower bounds for sorting with realistic instruction sets,” IEEE Trans. on Computers C-34:4 (1985) 311–317.
D. Dobkin and R. J. Lipton, “A lower bound of 1/2n2 on linear search programs for the knapsack problem,” J. of Computer and System Sciences 16 (1978) 413–417.
D. Dobkin and R. J. Lipton, “On the complexity of computations under varying sets of primitives,” in Automata Theory and Formal Languages (edited by H. Bradhage), Lecture Notes in Computer Science 33, Springer-Verlag (1975), 110–117.
B. Just, F. Meyer auf der Heide and A. Wigderson, “On computations with integer division,” RAIRO Informatique Théorique 23 (1989), 101–111.
P. Klein and F. Meyer auf der Heide, “A lower time bound for the knapsack problem on random access machines,” Acta Informatica 19 (1983), 385–395.
K. Lürwer-Brüggemeier and F. Meyer auf der Heide, “Capabilities and complexity of computations with integer division,” Proc. 10th Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 665, Springer-Verlag (1993), 463–472.
Y. Mansour, B. Schieber and P. Tiwari, “Lower bounds for computations with the floor operation,” SIAM J. Comput. 20:2 (1991), 315–327.
Y. Mansour, B. Schieber and P. Tiwari, “A lower bound for integer greatest common divisor computations,” J. of the ACM 38 (1991) 453–471.
F. Meyer auf der Heide, “Lower bounds for solving linear diophantine equations on random access machines,” J. of the ACM 32:4 (1985), 929–937.
F. Meyer auf der Heide, “On genuinely time bounded computations,” Proc. 6th Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 349, Springer-Verlag (1989), 1–16.
W. Paul and J. Simon, “Decision trees and random access machines,” in Logic and Algorithmic, monographie nℴ30 de l'enseignement mathématique, Université de Genève 1982.
F. P. Preparata, and M. I. Shamos, Computational Geometry: An Introduction, 2nd printing, Springer-Verlag, 1985/1988.
A. C. Yao, “Lower bounds for algebraic computation trees with integer inputs,” SIAM J. Comput. 20:4 (1991), 655–668.
A. C. Yao, “Decision tree complexity and Betti numbers,” Proc. 26th Annual ACM Symp. on Theory of Computing (1994).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ben-Amram, A.M., Galil, Z. (1995). Lower bounds on algebraic random access machines. In: Fülöp, Z., Gécseg, F. (eds) Automata, Languages and Programming. ICALP 1995. Lecture Notes in Computer Science, vol 944. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60084-1_88
Download citation
DOI: https://doi.org/10.1007/3-540-60084-1_88
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60084-8
Online ISBN: 978-3-540-49425-6
eBook Packages: Springer Book Archive