Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/45751
Title: LOWER BOUNDS FOR THE COMPLEXITY OF FUNCTIONS IN A REALISTIC RAM MODEL
Authors: Bshouty, Nader H.
Keywords: Computer Science
Issue Date: 1-May-1995
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.
URI: http://hdl.handle.net/1880/45751
Appears in Collections:Bshouty, Nader

Files in This Item:
File Description SizeFormat 
1995-568-20.pdf1.9 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.