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 $\epsilon> 0$ so that if $n$ is sufficiently large then the

elements distinctness problem cannot be solved in time $kn$ with

$\epsilon 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. We also show

that there is a simple decision problem that can be solved in constant

time (actually in two steps) using non-deterministic computation, while

there is no deterministic linear time algorithm with $\epsilon n\log n$

bits read and write memory which solves the problem. More precisely if

we allow $kn$ time for some fixed constant $k$, then there is an

$\epsilon>0$ so that the problem cannot be solved with $\epsilon n\log

n$ bits of read and write memory if $n$ is sufficiently large. The

decision problem is the following: ``Find two different input registers,

so that the Hamming distance of their contents is at most $(1/4)c\log

n$". $1/4$ can be replaced by any fixed $0<\gamma <1/2$ if $c$ is

sufficiently large with respect to $\gamma$. We actually show that the

promise problem : ``decide whether all occurring Hamming distances are

greater than $((1\over 2) -\gamma)c\log n$ or there is at least one

which is smaller than $\gamma c\log n$" where $\gamma>0$ is an

arbitrarily small constant, cannot be solved by a nonlinear algorithm

with the described limitations even if we know that we only get inputs

where one of these conditions hold. (In this case $\epsilon$ may depend

on $\gamma$ too).

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 $\epsilon> 0$ so that if $n$ is sufficiently large then the

elements distinctness problem cannot be solved in time $kn$ with

$\epsilon 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. We also show

that there is a simple decision problem that can be solved in constant

time (actually in two steps) using non-deterministic computation, while

there is no deterministic linear time algorithm with $\epsilon n\log n$

bits read and write memory which solves the problem. More precisely if

we allow $kn$ time for some fixed constant $k$, then there is an

$\epsilon>0$ so that the problem cannot be solved with $\epsilon n\log

n$ bits of read and write memory if $n$ is sufficiently large. The

decision problem is the following: ``Find two different input registers,

so that the Hamming distance of their contents is at most $(1/4)c\log

n$". $1/4$ can be replaced by any fixed $0<\gamma <1/2$ if $c$ is

sufficiently large with respect to $\gamma$. We actually show that the

promise problem : ``decide whether all occurring Hamming distances are

greater than $((1\over 2) -\gamma)c\log n$ or there is at least one

which is smaller than $\gamma c\log n$" where $\gamma>0$ is an

arbitrarily small constant, cannot be solved by a nonlinear algorithm

with the described limitations even if we know that we only get inputs

where one of these conditions hold. (In this case $\epsilon$ may depend

on $\gamma$ too).