Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions

摘要

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 value of the parameters which decides whether there are two different input registers whose contents are identical.