World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

ON HELPING AND INTERACTIVE PROOF SYSTEMS

    https://doi.org/10.1142/S012905419500010XCited by:7 (Source: Crossref)

    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 . 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.

    Remember to check out the Most Cited Articles!

    Check out these Handbooks in Computer Science