Direkt zum InhaltDirekt zur SucheDirekt zur Navigation
▼ Zielgruppen ▼
 

Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

If NP has Polynomial-Size Circuits, then MA = AM

Vikraman Arvind, Johannes Köbler, Uwe Schöning, and Rainer Schuler

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