ECCC-Report TR94-007https://eccc.weizmann.ac.il/report/1994/007Comments and Revisions published for TR94-007en-usMon, 12 Dec 1994 00:00:00 +0200
Paper TR94-007
| Computational Complexity and Knowledge Complexity |
Oded Goldreich,
Rafail Ostrovsky,
Erez Petrank
https://eccc.weizmann.ac.il/report/1994/007We study the computational complexity of languages which have
interactive proofs of logarithmic knowledge complexity. We show that
all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior
to this work, for languages with greater-than-zero knowledge
complexity (and specifically, even for knowledge complexity 1) only
trivial computational complexity bounds (i.e., recognizability in
${\cal PSPACE}={\cal 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., ${\cal SKC}(k(\cdot))\subseteq{\cal PKC}(k(\cdot)+\log(\cdot))$).
Mon, 12 Dec 1994 00:00:00 +0200https://eccc.weizmann.ac.il/report/1994/007