If NP has Polynomial-Size Circuits, then MA = AM
If NP has Polynomial-Size Circuits, then MA = AM
Vikraman Arvind, Johannes Köbler, Uwe Schöning, and Rainer
Schuler
Abstract:
Abstract:
It is shown that the assumption of NP having polynomial-size circuits implies (apart from a collapse of the polynomial-time hierarchy as shown by Karp and Lipton) that the classes AM and MA of Babai's Arthur-Merlin hierarchy coincide. This means that also a certain inner collapse of the remaining classes of the polynomial-time hierarchy occurs.
Ps-File: If NP has Polynomial-Size Circuits, then MA = AM
zuletzt geändert:
31.10.05
SK
Document Actions
Persönliche Werkzeuge
- Sie sind nicht eingeloggt.
- Log in
Deutsch
English