Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NONUNIFORM CLASSES:
Reports tagged with nonuniform classes:
TR99-033 | 19th August 1999
Vikraman Arvind, J. Köbler

Graph Isomorphism is Low for ZPP$^{\mbox{\rm NP}}$ and other Lowness results.

We show the following new lowness results for the probabilistic
class ZPP$^{\mbox{\rm NP}}$.

1. The class AM$\cap$coAM is low for ZPP$^{\mbox{\rm 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\$^{\mbox{\rm ... more >>>

ISSN 1433-8092 | Imprint