New Lower Bounds for Element Distinctness on a One-tape Turing Machine

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\Gamma n 2 = log n) for deterministic Turing machines and of \Omega\Gamma n log 2 n) [4] for nondeterministic Turing machines to \Omega\Gamma 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\Gamma maxfNn;Nmg). The proof makes use of Kolmogorov Complexity. Keywords: Theory of Computation, Kolmogorov Complexity 1 Introduction The study of lower bounds for any computational model is one of the most difficult problems in Computational Complexity. Recent developments in Kolmogorov Complexity have proven to be a useful tool for obtaining new bounds in Tu..