Element distinctness on one-tape Turing machines: a complete solution期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Element distinctness on one-tape Turing machines: a complete solution

Authors:	Amir?M?Ben-Amram Omer?Berkman Email author" target="_blank">Holger?Petersen Email 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 $m\ge\log n$ bits each on deterministic and nondeterministic one-tape Turing machines. We present an algorithm running in time $O(n^2m(m+2-\log n))$ for deterministic machines and nondeterministic solutions that are of time complexity $O(nm(n + \log m))$ . For elements of logarithmic size $m = O(\log n)$ , on nondeterministic machines, these results close the gap between the known lower bound $\Omega(n^2\log n)$ and the previous upper bound $O(n^2(\log n)^{3/2}(\log\log n)^{1/2})$ . 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 等数据库收录！