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