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).