Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Bounds for the Element Distinctness Problem on one-tape Turing machines
Autore:
Petersen, H;
Indirizzi:
Univ Stuttgart, Inst Comp Sci, D-70565 Stuttgart, Germany Univ Stuttgart Stuttgart Germany D-70565 Sci, D-70565 Stuttgart, Germany
Titolo Testata:
INFORMATION PROCESSING LETTERS
fascicolo: 2, volume: 81, anno: 2002,
pagine: 75 - 79
SICI:
0020-0190(20020131)81:2<75:BFTEDP>2.0.ZU;2-R
Fonte:
ISI
Lingua:
ENG
Keywords:
computational complexity; Element Distinctness Problem; Turing machines;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
10
Recensione:
Indirizzi per estratti:
Indirizzo: Petersen, H Univ Stuttgart, Inst Comp Sci, Breitwiesenstr 20-22, D-70565 Stuttgart, Germany Univ Stuttgart Breitwiesenstr 20-22 Stuttgart Germany D-70565
Citazione:
H. Petersen, "Bounds for the Element Distinctness Problem on one-tape Turing machines", INF PROCESS, 81(2), 2002, pp. 75-79

Abstract

We disprove a conjecture of Lopez-Ortiz by showing that the Element Distinctness Problem for n numbers of size O(logn) can be solved in O(n(2)(logn)(3/2)(loglogn)(1/2)) steps by a nondeterministic one-tape Turing machine. Further we give a simplified algorithm for solving the problem for shorter numbers in time O(n(2) log n) on a deterministic one-tape Turing machine and a new proof of the matching lower bound. (C) 2002 Elsevier Science B.V All rights reserved.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 18/01/20 alle ore 01:41:23