Interactive Proof Systems with Public Coin: Lower Space Bounds and Hierarchies of Complexity Classes
Title | Interactive Proof Systems with Public Coin: Lower Space Bounds and Hierarchies of Complexity Classes |
Publication Type | Technical Report |
Year of Publication | 1996 |
Authors | Liskiewicz, M. |
Other Numbers | 1056 |
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. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1996/tr-96-047.pdf |
Bibliographic Notes | ICSI Technical Report TR-96-047 |
Abbreviated Authors | M. Liskiewicz |
ICSI Publication Type | Technical Report |