New Lower Bounds for Element Distinctness on a One-tape Turing Machine
[.ps]
[.pdf]
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(
n2/log n) for deterministic Turing machines and of Omega(
n log2 n) for nondeterministic Turing machines to Omega(
n2 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.
Bibtex Entry
