New Lower Bounds for Element Distinctnes
s on a One-tape Turing Machine. A. Lopez-Ortiz. Information
Processing Letters. 51 (1994) 311-314.
PostScript file.
Abstract.
It is shown that the Element Distinctness
Problem (n numbers of k log n bits each, k > 2)
on a one-tape Turing machine takes time proportional
to almost the square of the size of the input. The proof holds for
both deterministic and nondeterministic Turing machines.
This proof improves the best known
lower bound of Omega(n^2/log n) for deterministic Turing machines
and of Omega(n log^2 n) for nondeterministic
Turing machines to Omega(n^2 log n).
The lower bound is generalized to the n-Element Distinctness
problem; on inputs of size N=nm, with 1 < n < N/log N, it
is shown to take time Omega(max{Nn,Nm}). The proof makes
use of Kolmogorov Complexity.