A note on the density of oracle decreasing time-space complexity. (English) Zbl 0821.68066
Summary: We study bounds on the density of oracles which can help to decrase 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č (1991).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Baker, T.; Gill, J.; Solovay, R., Relativizations of the P =?NP question, SIAM J. Comput., 4-4, 431-442 (1975) · Zbl 0323.68033 |
| [2] | Balcazar, J.; Diaz, J.; Gabarro, J., Structural Complexity II, EATCS Monographs on Theoret. Comput. Sci., Vol. 22 (1988) · Zbl 0638.68040 |
| [3] | Book, R. V., Towards a theory of relativization: Positive relativizations, (Proceedings of the 4th STACS ’87. Proceedings of the 4th STACS ’87, Lecture Notes in Computer Science, Vol. 247 (1987), Springer: Springer Berlin), 1-21 · Zbl 0627.03020 |
| [4] | Cobham, A., The recognition problem for perfect squares, (Proceedings of the 7th IEEE Symp. on SWAT (1966), Berkeley), 78-87 |
| [5] | Harmanis, J.; Chang, R.; Chari, S.; Ranjan, D.; Rohatgi, P., Relativization: a revisionistic retrospective, Bullet. EATCS, 47, 144-153 (1992) · Zbl 0746.68033 |
| [6] | Hromkovicˇ, J., On problems for which no oracle can help, Math. Systems Theory, 24, 41-52 (1991) · Zbl 0674.68031 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
