Lower Bounds for the Complexity of Funct
โ
Nader H. Bshouty
๐
Article
๐
1999
๐
Elsevier Science
๐
English
โ 127 KB
This paper develops a new technique that finds almost tight 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 ร 4 operations q, y, = , the standard bit operation Shift, Ro