Direkt zum Inhalt

New Lowness Results for ZPP(NP) and other Complexity Classes

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
zuletzt geändert: 31.10.05 SK
Document Actions
Persönliche Werkzeuge
« August 2008 »
Mo Di Mi Do Fr Sa So
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31