A NOTE ON THE DENSITY OF ORACLE DECREASING TIME-SPACE COMPLEXITY

Authors
DURIS P ROLIM JDP
Citation
P. Duris et Jdp. Rolim, A NOTE ON THE DENSITY OF ORACLE DECREASING TIME-SPACE COMPLEXITY, Theoretical computer science, 132(1-2), 1994, pp. 435-444
Citations number
6
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
132
Issue
1-2
Year of publication
1994
Pages
435 - 444
Database
ISI
SICI code
0304-3975(1994)132:1-2<435:ANOTDO>2.0.ZU;2-U
Abstract
In this paper we study bounds on the density of oracles which can help to decrease the time-space complexity of recognition of a particular language by off-line multitape Turing machines. We establish an upper and a lower bound on the density of such oracles which are optimal up to a multiplicative constant and improve the bounds stated by Hromkovi c (1991).