Our computational model is a random access machine with n read only input registers each containing measure the time by the number of accesses to the input registers.We show that for all k there is an #epsilon#>0 so that if n is sufficiently large then the elements distinctness problem cannot be solved in time kn with #epsilon#nbits 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.
展开▼
