On the knowledge complexity of 𝒩𝒫

The authors show that if a language has an interactive proof of logarithmic statistical knowledge-complexity, then it belongs to the class 𝒜ℳ∩co-𝒜ℳ. Thus, if the polynomial time hierarchy does not collapse, then 𝒩𝒫-complete languages do not have logarithmic knowledge complexity. Prior to this work, there was no indication that would contradict 𝒩𝒫 languages being proven with even one bit of knowledge. Next, they consider the relation between the error probability and the knowledge complexity of an interactive proof. They show that if the error probability ε(n) is less than 2 ^-3k(n) (where k(n) is the knowledge complexity) then the language proven has to be in the third level of the polynomial time hierarchy. In order to prove their main result, they develop an 𝒜ℳ protocol for checking that a samplable distribution has a given entropy. They believe that this protocol is of independent interest