We study the computational complexity of languages which haveinteractive proofs of logarithmic knowledge complexity. We show thatall such languages can be recognized in . Priorto this work, for languages with greater-than-zero knowledgecomplexity (and specifically, even for knowledge complexity 1) onlytrivial computational complexity bounds (i.e., recognizability in=) were known. In the course of our proof, werelate statistical knowledge-complexity with perfectknowledge-complexity; specifically, we show that, for the honestverifier, these hierarchies coincide, up to a logarithmic additive term (i.e., (k())(k()+log())).
展开▼
