# Technical Report CS0862

 TR#: CS0862 Class: CS Title: COMPUTATIONAL COMPLEXITY AND KNOWLEDGE COMPLEXITY. Authors: O. Goldreich, R. Ostrovsky and E. Petrank PDF CS0862.pdf 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 knowledgeable complexity 1) only trivial computational complexity bounds (i.e., 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(\cdot)) \subseteq PKC(k(\cdot)+ \log(\cdot))$). Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1995/CS/CS0862), rather than to the URL of the PDF files directly. The latter URLs may change without notice.