On the knowledge complexity of \(\mathcal N\mathcal P\) (Q1848028)

The paper is the journal version of an article with the same title that appeared at FOCS'96. It investigates the relation between computational complexity and knowledge complexity. The main result is that languages having an interactive proof with logarithmic knowledge complexity are in \({\mathcal AM}\) \(\cap\) co-\({\mathcal AM}\), where \({\mathcal AM}\) denotes the class of problems with constant round interactive proofs. By a result of \textit{R. B. Boppana}, \textit{J. Håstad} and \textit{St. Zachos} [Inf. Process. Lett. 25, 127-132 (1987; Zbl 0653.68037)], we know that the class \({\mathcal NP}\) of languages that can be recognized in non-deterministically polynomial time is not fully contained in co-\({\mathcal AM}\) unless the polynomial time hierarchy collapses. But then the authors have actually shown that \({\mathcal NP}\)-complete problems do not have logarithmic knowledge complexity unless the polynomial time hierarchy collapses. As a byproduct of the proof of the main result, the authors present an AM protocol for approximating the entropy of a samplable distribution, which is interesting on its own. Moreover, the intermediate results along the way towards the main result can also be used to address another important issue, namely the connection between the soundness error probability of an interactive proof and its knowledge complexity. Specifically, the authors show that if a language has an interactive proof with a small soundness error compared to its knowledge complexity, then this language has limited computational complexity. The paper is well-written. The authors take great efforts to make the presentation as self-contained as possible by carefully recalling the required notions. This together with a detailed overview of related works makes the paper also accessible to readers not so familiar with knowledge complexity etc. Moreover, of all the results derived in this paper, the authors discuss the consequences and the intuitive meaning of these results. Finally, a whole section is devoted to a sketch of the techniques presented in \textit{W. Aiello} and \textit{J. Håstad} [Inf. Comput. 93, 233-240 (1991; Zbl 0734.68043)], where a related result was derived. It is pointed out, which elements of that method were taken over in the present paper and why the method presented there does not suffice to derive the results of the present paper.