Abstract.
One of the many contributions of the paper of Goldwasser, Micali and Rackoff is the introduction of the notion of knowledge complexity. Knowledge complexity zero (also known as zero-knowledge) has received most of the attention of the authors and all the attention of their followers. In this paper, we present several alternative definitions of knowledge complexity and investigate the relations between them.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: July 22, 1997.
Rights and permissions
About this article
Cite this article
Goldreich, O., Petrank, E. Quantifying knowledge complexity. Comput. complex. 8, 50–98 (1999). https://doi.org/10.1007/s000370050019
Issue Date:
DOI: https://doi.org/10.1007/s000370050019