Element Distinctness and Sorting on One-Tape Off-Line Turing Machines
We investigate off-line Turing machines equipped with a two-way input-tape and one work-tape.
- PDF / 375,231 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 20 Downloads / 227 Views
stract. We investigate off-line Turing machines equipped with a twoway input-tape and one work-tape. It is shown that the Element Distinctness Problem (EDP) for m binary strings of length = O(m/ log2 m) can be solved in time O(m3/2 1/2 ) and space O(m1/2 1/2 ) on a nondeterministic machine. This is faster than the best sorting algorithm on the computational model and optimal if time and space are considered simultaneously. For deterministic machines we give an optimal algorithm that can sort m binary strings consisting of bits each in O(m3/2 ) steps, provided that = O(m1/4 ). By modifying the solution we obtain the time bound O(m3/2 ) and the space bound O(m1/2 2 ) for the EDP.
1
Introduction
The Element Distinctness Problem (EDP) is a well known benchmark task for a variety of models of computation ranging from single-tape Turing machines [1,8,9,11] to Quantum Computers [3]. The input for the EDP (sometimes called Element Uniqueness Problem) is a multiset of m binary strings of length each. Here is determined by some function of m. Of course ≥ log m and typically = Θ(log m). The question to be answered is, whether every element in the input occurs exactly once. The EDP is closely related to sorting, since on most computational models an efficient reduction from EDP to sorting is easily accomplished. Therefore lower bounds for EDP generalize to sorting, while EDP as a decision problem might be easier to analyze. For these reasons it is interesting to study upper and lower bounds for EDP and compare them to the most efficient sorting algorithms on different computational models. On single-tape Turing machines (no separate input tape) several authors have investigated the complexity of the EDP [8,9,11] until it was completely determined in [1]. We continue this research by moving on to a more powerful model of computation, the off-line Turing machine. For this type of machine lower and upper bounds on the complexity of sorting are known in the deterministic and nondeterministic mode of operation [4,12]. In fact off-line Turing machines are among the most powerful models of computation for which non-trivial lower V. Geffert et al. (Eds.): SOFSEM 2008, LNCS 4910, pp. 406–417, 2008. c Springer-Verlag Berlin Heidelberg 2008
Element Distinctness and Sorting on One-Tape Off-Line Turing Machines
407
bounds on natural problems could be shown. Upper bounds indicate to what extent our techniques for establishing lower bounds can be improved. This paper is organized as follows. In Section 2 the necessary definitions are given. We present a nondeterministic solution of EDP and a matching lower bound in Section 3. There are at least two reasons for considering these results first. A nondeterministic Turing machine can guess very useful information that a deterministic machine would have to tediously compute (if possible at all). Therefore the algorithm tends to be simpler than a deterministic counterpart. The second aspect is that a solution to EDP can reject immediately once it discovers that an element appears twi
Data Loading...
