Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Vikraman Arvind and Johannes Köbler

Abstract: We show the following new lowness results for the probabilistic class ZPP^NP.

• The class AM \cap coAM is low for ZPP^NP. As a consequence it follows that Graph Isomorphism and several group-theoretic problems known to be in AM \cap coAM are low for ZPP^NP.
• The class IP[P/poly], consisting of sets that have interactive proof systems with honest provers in P/poly, is also low for ZPP^NP.

We consider lowness properties of nonuniform function classes, namely, NPMV/poly, NPSV/poly, NPMV_t/poly, and NPSV_t/poly. Specifically, we show that

• Sets whose characteristic functions are in NPSV/poly and that have program checkers (in the sense of Blum and Kannan) are low for AM and ZPP^NP.
• Sets whose characteristic functions are in NPMV_t/poly are low for \Sigma_2^p.

Ps-File: New Lowness Results for ZPP(NP) and other Complexity Classes