New Lowness Results for ZPPNP and Other Complexity Classes

摘要

We show that the class AM∩coAM is low for ZPPNP. As a consequence, it follows that Graph Isomorphism and several group-theoretic problems are low for ZPPNP. We also show that the class IP[P/poly], consisting of sets that have interactive proof systems with honest provers in P/poly, is also low for ZPPNP. For the nonuniform function classes NPMV/poly, NPSV/poly, and NPMVt/poly, we show the following lowness results: Sets whose characteristic functions are in NPSV/poly and that have program checkers are low for AM and ZPPNP. Self-reducible sets with characteristic functions in NPMVt/poly are low for Σ2p. Sets whose characteristic functions are in NPMV/poly and that have program checkers are low for Σ2p. We also give applications of these lowness results.