Element distinctness on one-tape Turing machines: a complete solution |
| |
Authors: | Amir?M?Ben-Amram Omer?Berkman Email author" target="_blank">Holger?PetersenEmail author |
| |
Affiliation: | (1) The Academic College of Tel-Aviv-Yaffo, 4 Antokolski St., 64044 Tel-Aviv, Israel;(2) University of Stuttgart, Breitwiesenstr. 20-22, 70565 Stuttgart, Germany |
| |
Abstract: | We give a complete characterization of the complexity of the element distinctness problem for n elements of
bits each on deterministic and nondeterministic one-tape Turing machines. We present an algorithm running in time
for deterministic machines and nondeterministic solutions that are of time complexity
. For elements of logarithmic size
, on nondeterministic machines, these results close the gap between the known lower bound
and the previous upper bound
. Additional lower bounds are given to show that the upper bounds are optimal for all other possible relations between m and n. The upper bounds employ hashing techniques, while the lower bounds make use of the communication complexity of set disjointness.Received: 23 April 2001, Published online: 2 September 2003Holger Petersen: Supported by Deutsche Akademie der Naturforscher Leopoldina , grant number BMBF-LPD 9901/8-1 of Bundesministerium für Bildung und Forschung . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|