Details

Autor(en) / Beteiligte

• Arvind, Vikraman
• Köbler, Johannes
• Reichel, Horst
• Tison, Sophie

Titel

Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results

Ist Teil von

• Lecture notes in computer science, 2000, Vol.1770, p.431-442

Ort / Verlag

Germany: Springer Berlin / Heidelberg

Erscheinungsjahr

2000

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• We show the following new lowness results for the probabilistic class ZPPNP. The class AM ∩ coAM is low for ZPPNP. As a consequence it follows that Graph Isomorphism and several group-theoretic problems known to be in AM ∩ coAM are low for ZPPNP.The class IP[P/poly], consisting of sets that have interactive proof systems with honest provers in P/poly, is also low for ZPPNP. We consider lowness properties of nonuniform function classes, namely, NPMV/poly, NPSV/poly, NPMVt/poly, and NPSVt/poly. Specifically, we show that Sets whose characteristic functions are in NPSV/poly and that have program checkers (in the sense of [8]) are low for AM and ZPPNP.Sets whose characteristic functions are in NPMVt/poly are low for Σ2p