𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Generalized lowness and highness and probabilistic complexity classes

✍ Scribed by Andrew Klapper

Book ID
105457957
Publisher
Springer
Year
1989
Tongue
English
Weight
437 KB
Volume
22
Category
Article
ISSN
1433-0490

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

New Lowness Results for ZPPNP and Other
New Lowness Results for ZPPNP and Other Complexity Classes
✍ V. Arvind; Johannes KΓΆbler πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 242 KB

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