Abstract
This paper studies small space-bounded interactive proof systems (IPSs) using public coin tosses, respectively Turing machines with both nondeterministic and probabilistic states, that works with bounded number of rounds of interactions. For this model of computations new impossibility results are shown. As a consequence we prove that for sublogarithmic space bounds, IPSs working in k rounds are less powerful than systems of 2k k−1 rounds of interactions. It is well known that such a property does not hold for polynomial time bounds. Babai showed that in this case any constant number of rounds can be reduced to 2 rounds.
On leave of Institute of Computer Science, University of Wrocław. The research was supported by KBN Grant 2 P301 034 07.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
L. Babai, Trading group theory for randomness, in Proceedings of the 17th ACM Symposium on Theory of Computing, ACM Press, 1985, 421–429.
A. Condon, Computational model of games, MIT Press, 1989.
S. Dwork and L. Stockmeyer, Finite state verifiers I: the power of interaction, Journal of the ACM, 39, 1992, 800–828.
R. Freivalds, Fast probabilistic algorithms, in Proceedings of the 8th International Symposium on Mathematical Foundations of Computer Science, Springer-Verlag, Heidelberg, 1979, 57–69.
R. Freivalds, Probabilistic 2-way machines, in Proceedings of the 10th International Symposium on Mathematical Foundations of Computer Science, Springer-Verlag, Heidelberg, 1981, 33–45.
J. Gill, Computational complexity of probabilistic Turing machines, SIAM Journal on Computing, 7, 1977, 675–695.
S. Goldwasser and M. Sipser, Private coins versus public coins in interactive prove systems, in Proceedings of the 18th ACM Symposium on Theory of Computing, ACM Press, 1986, 59–68.
M. Liśkiewicz and R. Reischuk, The sublogarithmic alternating space world, SIAM Journal on Computing, 24, 1996, 828–861.
M. Liśkiewicz and R. Reischuk, Space Bounds for Interactive Proof Systems with Public Coins and Bounded Number of Rounds, ICSI Technical Report No. TR-96-025, Berkeley, July 1996.
I. Macarie, Space-bounded probabilistic computation: old and new stories, SIGACT News, vol. 26(3), 1995, 2–12.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liśkiewicz, M. (1997). Interactive proof systems with public coin: Lower space bounds and hierarchies of complexity classes. 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/BFb0023454
Download citation
DOI: https://doi.org/10.1007/BFb0023454
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