New lowness results for ZPP (NP) and other complexity classes
V. Arvind, Johannes Köbler · edoc Publication server (Humboldt University of Berlin) · 2005
We show that the class AM coAM is low for ZPP NP . As a consequence, it follows that Graph Isomorphism and several group-theoretic problems are low for ZPP NP . 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 ZPP NP . 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 ZPP NP . Self-reducible sets with characteristic functions in NPMVt=poly are low for S p . Sets whose characteristic functions are in NPMV=poly and that have program checkers are low for S p . We also give applications of these lowness results. # 2002 Elsevier Science (USA)