Abstract
This paper develops a new technique that finds lower bounds for the
complexity of programs that compute or approximate functions in a
realistic RAM model. The nonuniform realistic RAM model
is a model that uses the arithmetic operations {+, -, x}, the
standard bit operations Shift, Rotate, AND, OR, XOR, NOT
(bitwise), comparisons and indirect addressing. We prove general results
that give almost tight bounds for the complexity of computing and
approximating functions in this model. The functions considered here are
integer division, modulo, square root, gcd and logarithms.
We also show that if we add the integer division to the realistic RAM
model then no nontrivial lower bound can be proven.
Our results can be also generalized to probabilistic, nondeterministic
and parallel RAM models.
Notes
We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca