Abstract
Vikraman Arvind, Johannes Köbler, and Rainer Schuler
Abstract:
We investigate the complexity of honest provers in interactive proof
systems. This corresponds precisely to the complexity of oracles
helping the computation of robust probabilistic oracle machines. We
obtain upper bounds for languages in FewEXP and for sparse sets in
NP. Further, interactive protocols with provers that are reducible to
sets of low information content are considered. Specifically, if the
verifier communicates only with provers in P/poly, then the accepted
language is low for Sigma^P_2. In the case that the provers are
polynomial-time reducible to log*-sparse sets or to sets in
strong-P/log then the protocol can be simulated by the verifier even
without the help of provers. As a consequence we obtain new collapse
results under the assumption that intractable sets reduce to sets with
low information content.