Computational Complexity and Knowledge Complexity.
Oded Goldreich, Rafail Ostrovsky, Erez Petrank
Abstract: We study the computational complexity of languages which have interactive proofs that do not reveal too much knowledge. That is, we consider languages with interactive proofs of logarithmic knowledge complexity. We show that all such languages can be recognized in ${\cal BPP}^{\cal NP}$. %probabilistic polynomial time with access to an NP oracle. Prior to this work, only trivial computational complexity bounds (i.e., recognizability in ${\cal PSPACE}={\cal IP}$) were known for languages with greater-than-zero knowledge complexity (and specifically, even for knowledge complexity 1). In 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., ${\cal SKC}(k(\cdot))\subseteq{\cal PKC}(k(\cdot)+\log(\cdot))$).
comment: Preliminary version appeared in the Twenty-sixth ACM Symposium on Theory of Computing (STOC-94) Full version in SIAM Journal on Computing, 27(4):1116-1141, August 1998.
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |