{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:02:08Z","timestamp":1787385728987,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>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 ${\\cal BPP}^{\\cal NP}$. Prior to this work, for languages with greater-than-zero knowledge complexity only trivial computational complexity bounds were known. In the course of our proof, we relate statistical knowledge complexity to perfect knowledge complexity; specifically, we show that, for the honest verifier, these hierarchies coincide up to a logarithmic additive term.<\/jats:p>","DOI":"10.1137\/s0097539795280524","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1116-1141","source":"Crossref","is-referenced-by-count":9,"title":["Computational Complexity and Knowledge Complexity"],"prefix":"10.1137","volume":"27","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erez","family":"Petrank","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"W. Aiello, M. Bellare, and R. Venkatesan,\n                      Knowledge on the average \u2013 Perfect, statistical and logarithmic\n                      , in Proceedings of the 27th Annual ACM Symposium on the Theory of Computing, Association for Computing Machinery, New York, 1995.","DOI":"10.1145\/225058.225186"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"W. Aiello and J. H\u00e5stad,\n                      Perfect zero\u2010knowledge can be recognized in two rounds\n                      , in Proc. 28th Annual IEEE Symposium on the Foundations of Computer Science, IEEE, Piscataway, NJ, 1987.","DOI":"10.1109\/SFCS.1987.47"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"L. Babai,\n                      Trading group theory for randomness\n                      , in Proc. 17th Annual ACM Symposium on the Theory of Computing, Association for Computing Machinery, New York, 1985.","DOI":"10.1145\/22145.22192"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Micali, and R. Ostrovsky,\n                      The (true) complexity of statistical zero\u2010knowledge\n                      , in Proc. 22nd Annual ACM Symposium on the Theory of Computing, Association for Computing Machinery, New York, 1990.","DOI":"10.1145\/100216.100285"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"M. Bellare and E. Petrank,\n                      Making zero\u2010knowledge provers efficient\n                      , in Proc. 24th Annual ACM Symposium on the Theory of Computing, Association for Computing Machinery, New York, 1992.","DOI":"10.1145\/129712.129781"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Michael Ben\u2010Or, Oded Goldreich, Shafi Goldwasser, Johan H\u00e5stad, Joe Kilian, Silvio Micali, Phillip Rogaway, Everything provable is provable in zero\u2010knowledge, Lecture Notes in Comput. Sci., Vol. 403, Springer, Berlin, 1990, 37\u20135691d:68026","DOI":"10.1007\/0-387-34799-2_4"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90232-8"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.2190\/4U1D-VQRM-J70D-JEQF"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"O. Goldreich, Y. Mansour, and M. Sipser,\n                      Interactive proof systems: Provers that never fail and random selection\n                      , in Proc. 28th Annual IEEE Symposium on the Foundations of Computer Science, IEEE, Piscataway, NJ, 1987.","DOI":"10.1109\/SFCS.1987.35"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050019"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"R15","first-page":"73","volume":"5","author":"Goldwasser S.","year":"1989","journal-title":"Adv. Comput. Res."},{"key":"R16","unstructured":"J. H\u00e5stad,\n                      Perfect zero\u2010knowledge in \ud835\udc9c\u2133\u2229\ud835\udcb8\u2134\u2010\ud835\udc9c\u2133\n                      , 1994, manuscript. Explains the underlying ideas behind."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and M. Yung,\n                      Direct minimum\u2010knowledge computations\n                      , in Advances in Cryptology\u2014Proceedings of CRYPTO 87, Lecture Notes in Computer Science 293, Springer\u2010Verlag, Berlin, New York, 1987.","DOI":"10.1007\/3-540-48184-2_4"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Carsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan, Algebraic methods for interactive proof systems, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 2\u20131092m:68105","DOI":"10.1109\/FSCS.1990.89518"},{"key":"R20","unstructured":"R. Ostrovsky,\n                      One\u2010way functions, hard on average problems, and statistical zero\u2010knowledge proofs\n                      , in Proc. Structures in Complexity Theory 6th Annual Conference IEEE, Piscataway, NJ, 1991."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky and A. Wigderson,\n                      One\u2010way functions are essential for non\u2010trivial zero\u2010knowledge\n                      , in Proc. 2nd Israeli Symp. on Theory of Computing and Systems, IEEE, Piscataway, NJ, 1993, pp. 3\u201317.","DOI":"10.1109\/ISTCS.1993.253489"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Erez Petrank, G\u00e1bor Tardos, On the knowledge complexity of NP, IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, 494\u20135031450647","DOI":"10.1109\/SFCS.1996.548508"},{"key":"R23","unstructured":"Adi Shamir, IP=PSPACE, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 11\u20131592j:68038"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"M. Sipser,\n                      A complexity theoretic approach to randomness\n                      , in Proc. 15th Annual ACM Symposium on the Theory of Computing, Association for Computing Machinery, New York, 1983.","DOI":"10.1145\/800061.808762"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"L. Stockmeyer,\n                      The complexity of approximate counting\n                      , in Proc. 15th Annual ACM Symposium on the Theory of Computing, Association for Computing Machinery, New York, 1983.","DOI":"10.1145\/800061.808740"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795280524","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:09Z","timestamp":1787335929000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795280524"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795280524"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795280524","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}