Space Bounds for Interactive Proof Systems with Public Coins and Bounded Number of Rounds

TitleSpace Bounds for Interactive Proof Systems with Public Coins and Bounded Number of Rounds
Publication TypeTechnical Report
Year of Publication1996
AuthorsLiskiewicz, M., & Reischuk R.
Other Numbers1035
Abstract

This paper studies interactive proof systems using public coin tosses, respectively Arthur-Merlin games, with a sublogarithmic space-bounded verifier. We provide examples of specific languages and show that such systems working with bounded number of rounds of interaction are unable to accept these languages. As a consequence, a separation of the second and the third level of the round/alternation hierarchy is obtained. It is well known that such a property does not hold for the corresponding polynomial time classes: in ["Proceedings of the 17th ACM Symposium on Theory of Computing", ACM Press, 1985, 421-429] Babai showed that the hierarchy of complexity classes AM_kTime(POL) collapses to the second level.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1996/tr-96-025.pdf
Bibliographic Notes

ICSI Technical Report TR-96-025

Abbreviated Authors

M. Liskiewicz and R. Reischuk

ICSI Publication Type

Technical Report