Topological lower bounds on algebraic random access machines
We prove general lower bounds for set recognition on random access machines (RAMs) that operate on real numbers with algebraic operations {+, -, x, /}, as well as RAMs that use the operations {+, -, x, left perpendicular right perpendicular}. 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 Wdegrees, the topological interior of W. Two results use ((W) over bar)degrees, 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 {+, -, x, /} or {+,- x, left perpendicular right perpendicular}. 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.).
algebraic computation trees element distinctness knapsack component counting arguments