DIMACS Princeton Theory Lunch
On the Knowledge Comlexity of NP
- Gabor Tardos
- Institute for Advanced Study
- Room 402, Computer Science (CS) Bldg, 35 Olden St.
- Princeton University, Princeton, NLJ
- 12:10 p.m. - Lunch will be served at ll:45 a.m.
- Thursday, September 26, 1996
Knowledge complexity measures how much a party gains from
an interaction with another (possibly stronger) party.
Making sure that a party learns nothing or very little
>from an interaction is a fundamental issue in cryptography,
hence the extensive study of the special case of zero knowledge
complexity. We consider Knowledge Complexity to be also a fundamental
issue in complexity, where we would like to understand not only the
computational abilities of machines working on their own, but also
their computational abilities following an interaction with the rest
of the world.
In this work, we study "what can be done" in low knowledge
complexity. In particular, we ask which languages can be proven
in low knowledge complexity. We show that all languages which
have interactive proofs with logarithmic knowledge complexity are
in the classes AM and co-AM. Since co-AM does not contain NP unless the
Polynomial Time Hierarchy (PH) collapses, NP-complete langauges are not likely
to have interactive proofs that do not yield to the verifier super-logarithmic
knowledge. Additional results will be discussed in the talk.
This work is a joint work with Erez Petrank.
Document last modified on September 20, 1996