Technical Report CS0862

TR#:CS0862
Class:CS
Title: COMPUTATIONAL COMPLEXITY AND KNOWLEDGE COMPLEXITY.
Authors: O. Goldreich, R. Ostrovsky and E. Petrank
PDFCS0862.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))$).
CopyrightThe 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.

To the list of the CS technical reports of 1995
To the main CS technical reports page

Computer science department, Technion
admin