Abstract
It is a fundamental problem in the randomized computation how to separate different randomized time or randomized space classes (c.f., e.g., [KV87, KV88]). We have separated randomized space classes below log n in [FK94]. Now we have succeeded to separate small randomized time classes for multi-tape 2-way Turing machines. Surprisingly, these “small” bounds are of type n+f(n) with f(n) not exceeding linear functions. This new approach to “sublinear” time complexity is a natural counterpart to sublinear space complexity. The latter was introduced by considering the input tape and the work tape as separate devices and distinguishing between the space used for processing information and the space used merely to read the input word from. Likewise, we distinguish between the time used for processing information and the time used merely to read the input word.
Research partially supported by Grant No.93-599 from the Latvian Council of Science
Research partially supported by the International Computer Science Institute, Berkeley, California, by the DFG grant KA 673/4-1, and by the ESPRIT BR Grants 7079 and ECUS030
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Freivalds, R., Fast computations by probabilistic Turing machines, Proceedings of Latvian State University, 233(1975), pp. 201–205 (Russian)
Freivalds, R., Probabilistic machines can use Isess runnning time, Information Processing'77 (Proc. IFIP Congress'77), North Holland, 1977, pp. 839–842
Freivalds, R., Speeding up recognition of some sets by usage of random number generators, Problemi kibernetiki, 36(1979), pp. 209–224 (Russian)
Freivalds, R., Probabilistic two-way machines, LNCS, 118(1981), pp.33–45
Freivalds, R., Space and reversal complexity of probabilistic one-way Turing machines, LNCS, 158(1983), pp. 159–170
Freivalds, R., Space and reversal complexity of probabilistic one-way Turing machines, Annals of Discrete Mathematics, 24(1985), pp. 39–50
Freivalds, R., Ikaunieks, E., On advantages of nondeterministic machines over probabilistic ones, Izvestiya VUZ. Matematika, No.2(177), 1977, pp.108–123 (Russian)
Freivalds, R., Karpinski, M., Lower space bounds for randomized computation, Lecture Notes in Computer Science, vol. 820(1994), pp. 580–592
Gallager, R.G., Information Theory and Reliable Communication. John Wiley, NY, 1968
Ja'Ja', J., Prasanna Kumar, V.K., Simon, J., Information transfer under different sets of protocols, SIAM J. Computation, 13(1984), pp.840–849
Kaneps, J. and Freivalds R., Minimal nontrivial space complexity of probabilistic one-way Turing machines, LNCS, 452(1990), pp. 355–361
Karpinski, M. and Verbeek, R., On the Monte Carlo space constructible functions and space separation results for probabilistic complexity classes, Information and Computation, 75(1987), pp. 178–189
Karpinski, M. and Verbeek, R., Randomness, probability, and the separation of Monte Carlo time and space, LNCS, 270(1988), pp. 189–207
Karpinski, M. and Verbeek, R., On randomized versus deterministic computation, Proc. ICALP'93, LNCS, 700(1993), pp. 227–240
Ming Li, Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer, 1993
Stearns, R.E., Hartmanis, J., Lewis, P.M., Hiearchies of memory limited computations, Proc. IEEE Conference on Switch., Circuit Theory and Logical Design, 1965, pp. 179–190
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Freivalds, R., Karpinski, M. (1995). Lower time bounds for randomized computation. In: Fülöp, Z., Gécseg, F. (eds) Automata, Languages and Programming. ICALP 1995. Lecture Notes in Computer Science, vol 944. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60084-1_73
Download citation
DOI: https://doi.org/10.1007/3-540-60084-1_73
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60084-8
Online ISBN: 978-3-540-49425-6
eBook Packages: Springer Book Archive