Quantifying knowledge complexity

Authors
Goldreich, O Petrank, E
Citation
O. Goldreich et E. Petrank, Quantifying knowledge complexity, COMP COMPLE, 8(1), 1999, pp. 50-98
Citations number
30
Categorie Soggetti
Engineering Mathematics
Journal title
COMPUTATIONAL COMPLEXITY
ISSN journal
10163328 → ACNP
Volume
8
Issue
1
Year of publication
1999
Pages
50 - 98
Database
ISI
SICI code
1016-3328(1999)8:1<50:QKC>2.0.ZU;2-4
Abstract
One of the many contributions of the paper of Goldwasser, Micali and Rackof f is the introduction of the notion of knowledge complexity. Knowledge comp lexity zero (also known as zero-knowledge) has received most of the attenti on of the authors and all the attention of their followers. In this paper, we present several alternative definitions of knowledge complexity and inve stigate the relations between them.