Computational Complexity and Knowledge Complexity
Title | Computational Complexity and Knowledge Complexity |
Publication Type | Technical Report |
Year of Publication | 1994 |
Authors | Goldreich, O., Ostrovsky R., & Petrank E. |
Other Numbers | 893 |
Abstract | We study the computational complexity of languages which have interactive proofs of logarithmic knowledge complexity. We show that all such languages can be recognized in BPP^NP. Prior to this work, for languages with greater-than-zero knowledge complexity (and specifically, even for knowledge complexity 1) only trivial computational complexity bounds (i.e., only recognizability in PSPACE = IP) were known. In the course of our proof, we relate statistical knowledge-complexity with perfect knowledge-complexity; specifically, we show that, for the honest verifier, these hierarchies coincide, up to a logarithmic additive term (i.e., SKC(k(·)) ? PKC(k(·) + log(·))). |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1994/tr-94-023.pdf |
Bibliographic Notes | ICSI Technical Report TR-94-023 |
Abbreviated Authors | O. Goldreich, R. Ostrovsky, and E. Petrank |
ICSI Publication Type | Technical Report |