[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations

  • Probabilism
  • Conference paper
  • First Online:
STACS 97 (STACS 1997)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1200))

Included in the following conference series:

Abstract

The study of the computational power of randomized computations is one of the central tasks of complexity theory. The main aim of this paper is the comparison of the power of Las Vegas computation and deterministic respectively nondeterministic computation. An at most polynomial gap has been established for the combinational complexity of circuits and for the communication complexity of two-party protocols. We investigate the power of Las Vegas computation for the complexity measures of one-way communication, finite automata and polynomialtime relativized Turing machine computation.

  1. (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.

  2. (ii)

    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 root of the size of the minimal deterministic finite automaton recognizing L. Using a specific language we verify the optimality of this lower bound.

Note, that this result establishes for the first time an at most polynomial gap between Las Vegas and determinism for a uniform computing model.

  1. (iii)

    For relativized polynomial computations we show that Las Vegas can be even more powerful than nondeterminism with a polynomial restriction on the number of nondeterministic guesses.

On the other hand superlogarithmic many advice bits in nondeterministic computations can be more powerful than Las Vegas (even Monte Carlo) computations in a relativized word.

The work of this author has been supported by DFG Project HR 14/3-1.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Aho, A.V., Hopcroft, J.E., Yannakakis, M.: On notions of information transfer in VLSI circuits. In: Proc. 15th Annual ACM STOC, ACM 1983, 133–139.

    Google Scholar 

  2. Bovet,D.P., Crescenzi,P.: Introduction to the Theory of Complexity. Prentice Hall 1994.

    Google Scholar 

  3. Diaz, J. Torán, J.: Classes of bounded nondeterminism. Mathematical Systems Theory, 23 (1990), 21–32.

    Article  Google Scholar 

  4. Freivalds, R.: Probabilistic two-way machines. Lecture Notes in Computer Science 118, Springer-Verlag, Berlin 1981, 33–45.

    Google Scholar 

  5. Hromkovič, J., Schnitger, G.: On the power of the number of advice bits in non-deterministic computations. Proc. ACM STOC'96, ACM 1996, pp. 551–560.

    Google Scholar 

  6. Meyer, A.R., Fischer, M.J.: Economies of description by automata, grammars and formal systems. In: Proceedings 12th SWAT Symp. 1971, 188–191

    Google Scholar 

  7. Mehlhorn,K., Schmidt,E.: Las Vegas is better than determinism in VLSI and distributed computing. Proc. 14th ACM STOC'82, ACM 1982, pp. 330–337.

    Google Scholar 

  8. Yao, A.C.: Some complexity questions related to distributed computing. In: Proc. 11th Annual ACM STOC, ACM 1981, 308–311.

    Google Scholar 

  9. Csiszar, I., Körner, J.: Information theory: coding theorems for discrete memeoryless systems, Academic Press, 1986.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Comenius University, Mlynská dolina, 842 15, Bratislava, Slovakia

    Pavol Ďuriš

  2. Institut für Informatik, Universität zu Kiel, 24098, Kiel, Germany

    Juraj Hromkovič

  3. Centre Universitaire d'Informatique, Université de Genève, 1211, Genéve 4, Switzerland

    José D. P. Rolim

  4. Fachbereich Informatik, Johann Wolfgang Goethe-Universität Frankfurt, Robert Mayer Strasse 11-15, 60054, Frankfurt am Main, Germany

    Georg Schnitger

Authors
  1. Pavol Ďuriš
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Juraj Hromkovič
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. José D. P. Rolim
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Georg Schnitger
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Rüdiger Reischuk Michel Morvan

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ďuriš, P., Hromkovič, J., Rolim, J.D.P., Schnitger, G. (1997). Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations. In: Reischuk, R., Morvan, M. (eds) STACS 97. STACS 1997. Lecture Notes in Computer Science, vol 1200. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0023453

Download citation

  • DOI: https://doi.org/10.1007/BFb0023453

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-62616-9

  • Online ISBN: 978-3-540-68342-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation