Determinism versus non-determinism for linear time RAMs

Abstract

Our computational model is a random access machine with n read only input registers each containing c log n bits of information and a read and write memory. We measure the time by the number of accesses to the input registers. We show that for all k there is an ε>0 so that if n is sufficiently large then the elements distinctness problem cannot be solved in time kn with εn bits of read and write memory, that is, there is no machine with this values of the parameters which decides whether there are two different input registers whose contents are identical.