×

On helping and interactive proof systems. (English) Zbl 0953.68554

Du, Ding-Zhu (ed.) et al., Algorithms and computation. 5th international symposium, ISAAC ’94, Beijing, P. R. China, August 25-27, 1994. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 834, 137-145 (1994).
Summary: 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.
For the entire collection see [Zbl 0856.00036].

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
PDFBibTeX XMLCite