Knowledge complexity is intended to measure
the computational advantage gained by interaction.
Hence, something that can be obtained without interaction
is not considered knowledge.
The latter phrase is somewhat qualitative and supplies the
intuition underlying the definition of zero-knowledge
(i.e., knowledge complexity zero).
Quantifying the amount of knowledge gained by interaction,
in case it is not zero, is more problematic.
We stress that the definition of zero-knowledge does not
depend on the formulation of the *amount* of knowledge gained
since this definition addresses the case in which
*no* knowledge is gained.
Various formulations of knowledge-complexity are given and investiagted
in [Goldreich and Petrank (1991)].

The following papers can be obtained in PostScript (papers are ordered by the full author-list):

- O. Goldreich, R. Ostrovsky and E. Petrank,

Computational Complexity and Knowledge Complexity, revised March 1995. - O. Goldreich and E. Petrank, Quantifying Knowledge Complexity (1991), revised July 1997.

Back to Oded Goldreich's homepage or to the full list of papers.