The problem of space invariance for sequential machines (Q1102112)

The paper presents a detailed discussion of the following invariance thesis: There exists a standard class of machines (including Turing machines and usual RAM's) with the property that models in this class simulate each other with polynomially overhead in time and with constant factor overhead in space. It is pointed out that in the literature this thesis is not dealt with sufficiently carefully. In particular, there seems to be no general consensus about what the correct space measure for RAM's should be. The authors discuss several possible space measures for RAM's, two of them in more detail. One measure which charges the logarithm of the address of any used register \(R_ i\) plus the logarithm of the maximum value stored in this register during the computation seems to be the correct space measure for RAM's because it satisfies the invariance thesis. However, in the literature one usually uses a measure which neglects the logarithm of the adress. The authors wished to prove that this measure is incorrect, and in fact they succeeded in the on-line case: They exhibit a language which requires more space on a Turing machine than on a RAM which shows that in this case RAM's cannot be simulated by Turing machines with a constant factor overhead in space. On the other hand, for the off-line case such a simulation can be given which needs, however, an exponential time overhead. Thus the invariance thesis is only weakly satisfied: There exists a polynomial time simulation, and there exists a linear space simulation of RAM's by Turing machines, but nothing is known about a simulation which is simultaneously time and space efficient. To prove the simulation result in the off-line case the authors make use of a perfect hash function. A considerable part of the paper is devoted to proving the existence of ''good'' hash functions. Here the authors improve results on perfect hash functions by M. L. Fredman, J. Komlos and E. Szemeredi [J. Assoc. Comput. Mach. 31, 538-544 (1984; Zbl 0629.68068)] and by K. Mehlhorn [Data structures and algorithms 1: Sorting and searching (EATCS Monogr. Theor. Comput. Sci. 1) (1984; Zbl 0556.68001)].