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