On the Notion of Bit Complexity
Claus Diem · Bulletin of the European Association for Theoretical Computer Science · 2013
In many works in the fields of computational complexity, algorithmic number theory and mathematical cryptology as well as in related areas, claims on the running times of algorithms are made. However, often no computational model is given and the analysis is performed in a more or less ad hoc way, counting in an intuitive way “bit operations”. On the other hand, the computational model of a successor RAM with logarithmic cost function provides an adequate and formal basis for the analysis of the complexity of algorithms from a “bit oriented” point of view. This motivates the search for a result on the simulation of machines in a suitably defined general model by successor RAMs. In this work, a very general RAM model is defined, and then a “quasi-optimal” result on the simulation of such machines by successor RAMs is given.