Computational Complexity and Knowledge Complexity

TitleComputational Complexity and Knowledge Complexity
Publication TypeTechnical Report
Year of Publication1994
AuthorsGoldreich, O., Ostrovsky R., & Petrank E.
Other Numbers893
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(·))).

URLhttp://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