Computational complexity and knowledge complexity (extended abstract)
Oded Goldreich, Rafail Ostrovsky, Erez Petrank · 1994
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 B7VN7.Prior to this work, for languages with greaterthan-zero knowledge complexity (and specifically, even for knowledge complexity 1) only trivial computational complexity bounds (i.e., only recognizability in PSPAC& = ZP) were known.Inthe 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(.))g Pxc(k($) + log(.))).