Paper Info
Title
Topological Lower Bounds on Algebraic Random Access Machines
Abstract
We prove general lower bounds for set recognition on random access machines (RAMs) that operate on real numbers with algebraic operations $\{+,-,\times,/\}$, as well as RAMs that use the operations $\{+,-,\times,\lfloor\;\rfloor\}$. 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, four similar results apply to the number of connected components of $W^\circ$, the topological interior of W. Two results use $(\overline W)^\circ$, 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 $\{+,-,\times,/\}$ or $\{+,-,\times,\lfloor\;\rfloor\}$.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 the input is restricted to the integers. (For one result on this model, we require that all program constants be rational.)
Year
DOI
Venue
2001
10.1137/S0097539797329397
SIAM J. Comput.
Keywords
Field
DocType
test-for-integer instruction,real number,algebraic computation tree,general lower bound,algebraic operation,arbitrary real number,computation tree,memory address,connected component,instruction set,algebraic random access machines,topological lower bounds,lower bound,knapsack
Integer,Discrete mathematics,Topology,Combinatorics,Algebraic number,Symbolic computation,Connected component,Knapsack problem,Real number,Mathematics,Algebraic operation,Random access
Journal
Volume
Issue
ISSN
31
3
0097-5397
Citations 
PageRank 
References 
8
0.54
6
Authors
2
Name
Order
Citations
PageRank
Amir M Ben-Amram132730.52
Zvi Galil236341426.98