A note on the density of oracle decreasing time–space complexity
- Dˇurisˇ, Pavol
- Rolim, JoséD.P.
View in ORKG Publication date
September 1994
DOI Publisher
Published by Elsevier B.V. ISSN
0304-3975Abstract
AbstractIn 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 Hromkovicˇ(1991)