×

On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. (English) Zbl 1007.68065

Summary: The study of the computational power of randomized computations is one of the central tasks of complexity theory. The main goal of this paper is the comparison of the power of Las Vegas computation and deterministic respectively nondeterministic computation. We investigate the power of Las Vegas computation for the complexity measures of one-way communication, ordered binary decision diagrams, and finite automata.
(i) For the one-way communication complexity of two-party protocols we show that Las Vegas communication can save at most one half of the deterministic one-way communication complexity. We also present a language for which this gap is tight.
(ii) The result (i) is applied to show an at most polynomial gap between determinism and Las Vegas for ordered binary decision diagrams.
(iii) For the size (i.e., the number of states) of finite automata we show that the size of Las Vegas finite automata recognizing a language \(L\) is at least the square root of the size of the minimal deterministic finite automaton recognizing \(L\). Using a specific language we verify the optimality of this lower bound.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W20 Randomized algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Babai, L.; Frankl, P.; Simon, J., Complexity classes in communication complexity theory, in, 337-347 (1986)
[2] Mehlhorn, K., and Schmidt, E.1982, Las Vegas is better than determinism in VLSI and distributed computing, inProceedings, 14th ACM Symposium on Theory of Computing, San Francisco, CA, pp. 330-337.; Mehlhorn, K., and Schmidt, E.1982, Las Vegas is better than determinism in VLSI and distributed computing, inProceedings, 14th ACM Symposium on Theory of Computing, San Francisco, CA, pp. 330-337.
[3] Savitch, W. J., Relationships between nondeterministic and deterministic tape complexities, J. Comput. System Sci., 4, 177-192 (1970) · Zbl 0188.33502
[4] Dietzfelbinger, M.; Kutylowski, M.; Reischuk, R., Exact lower bounds for computing Boolean functions on CREW PRAMs, J. Comput. System Sci., 48, 231-254 (1994) · Zbl 0822.68049
[5] Bovet, D. P, and, Crescenzi, P. 1994, Introduction to the Theory of Complexity, Prentice Hall, New York.; Bovet, D. P, and, Crescenzi, P. 1994, Introduction to the Theory of Complexity, Prentice Hall, New York. · Zbl 0809.68067
[6] Yao, A. C.1981, Some complexity questions related to distributed computing, inProceedings, 11th ACM Symposium on Theory of Computing, pp. 308-311.; Yao, A. C.1981, Some complexity questions related to distributed computing, inProceedings, 11th ACM Symposium on Theory of Computing, pp. 308-311.
[7] Hromkovič, J. 1997, Communication Complexity and Parallel Computing, Springer-Verlag, Berlin.; Hromkovič, J. 1997, Communication Complexity and Parallel Computing, Springer-Verlag, Berlin.
[8] Kushilevitz, E, and, Nisan, N. 1997, Communication Complexity, Cambridge Univ. Press, Cambridge, UK.; Kushilevitz, E, and, Nisan, N. 1997, Communication Complexity, Cambridge Univ. Press, Cambridge, UK. · Zbl 0869.68048
[9] Aho, A. V., Hopcroft, J. E., and Yannakakis, M.1983, On notions of information transfer in VLSI circuits, inProceedings, 15th ACM Symposium on Theory of Computing, pp. 133-139.; Aho, A. V., Hopcroft, J. E., and Yannakakis, M.1983, On notions of information transfer in VLSI circuits, inProceedings, 15th ACM Symposium on Theory of Computing, pp. 133-139.
[10] Hromkovič, J., and Schnitger, G.1996, On the power of the number of advice bits in nondeterministic computations, inProceedings, 28th ACM Symposium on Theory of Computing, pp. 551-560.; Hromkovič, J., and Schnitger, G.1996, On the power of the number of advice bits in nondeterministic computations, inProceedings, 28th ACM Symposium on Theory of Computing, pp. 551-560.
[11] Bryant, R. E.1985, Symbolic manipulation of Boolean functions using a graphical representation, in22nd ACM/IEEE Design Automation Conf., pp. 688-694.; Bryant, R. E.1985, Symbolic manipulation of Boolean functions using a graphical representation, in22nd ACM/IEEE Design Automation Conf., pp. 688-694.
[12] Bryant, R. E., Graph-based algorithms for Boolean function manipulation, IEEE Trans. Comput., 35, 677-691 (1986) · Zbl 0593.94022
[13] Pudlák, P, and, Žák, S. 1983, Space Complexity of Computation, Technical Report, Prague.; Pudlák, P, and, Žák, S. 1983, Space Complexity of Computation, Technical Report, Prague.
[14] Wegener, I. 1987, The Complexity of Boolean Functions, Wiley-Teubner Series in Computer Science, Wiley, New York and Teubner, Stuttgart.; Wegener, I. 1987, The Complexity of Boolean Functions, Wiley-Teubner Series in Computer Science, Wiley, New York and Teubner, Stuttgart.
[15] Sauerhoff, M.1998, Lower bounds for randomized read-k-times branching programs, inProceedings, 15th Symposium on Theoretical Aspects in Computer Science, Lecture Notes in Computer Science, vol. 1373, pp. 105-115, Springer-Verlag, Berlin.; Sauerhoff, M.1998, Lower bounds for randomized read-k-times branching programs, inProceedings, 15th Symposium on Theoretical Aspects in Computer Science, Lecture Notes in Computer Science, vol. 1373, pp. 105-115, Springer-Verlag, Berlin.
[16] Klauck, H.2000, On quantum und probabilistic communication: Las Vegas and one-way protocols, inProceedings, 32th ACM Symposium on Theory of Computing, pp. 644-651.; Klauck, H.2000, On quantum und probabilistic communication: Las Vegas and one-way protocols, inProceedings, 32th ACM Symposium on Theory of Computing, pp. 644-651. · Zbl 1296.68058
[17] Newman, I., Private vs. common random bits in communication complexity, Inform. Process. Lett., 39, 301-315 (1991)
[18] Csiszar, I, and, Körner, J. 1986, Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press, New York.; Csiszar, I, and, Körner, J. 1986, Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press, New York.
[19] Papadimitriou, Ch.; Sipser, M., Communication complexity, J. Comput. System Sci., 28, 260-269 (1984) · Zbl 0584.68064
[20] Sieling, D.; Wegener, I., NC-algorithms for operations on binary decision diagrams, Parallel Process. Lett., 3, 3-12 (1993)
[21] Hromkovič, J., Relation between Chomsky hierarchy and communication complexity hierarchy, Acta Math. Univ. Comenian (N.S.), 48-49, 311-317 (1986) · Zbl 0631.68068
[22] Meyer, A. R., and Fischer, M. J.1971, Economies of description by automata, grammars and formal systems, inProceedings, 12th IEEE Symposium on Switching and Automata Theory, pp. 188-191.; Meyer, A. R., and Fischer, M. J.1971, Economies of description by automata, grammars and formal systems, inProceedings, 12th IEEE Symposium on Switching and Automata Theory, pp. 188-191.
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.