On the knowledge complexity of /spl Nscr//spl Pscr/
Erez Petrank, Gábor Tardos · 2002
The authors show that if a language has an interactive proof of logarithmic statistical knowledge-complexity, then it belongs to the class /spl Ascr//spl Mscr//spl cap/co-/spl Ascr//spl Mscr/. Thus, if the polynomial time hierarchy does not collapse, then /spl Nscr//spl Pscr/-complete languages do not have logarithmic knowledge complexity. Prior to this work, there was no indication that would contradict /spl Nscr//spl Pscr/ 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 /spl epsiv/(n) is less than 2/sup -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 /spl Ascr//spl Mscr/ protocol for checking that a samplable distribution has a given entropy. They believe that this protocol is of independent interest.