IF NP HAS POLYNOMIAL-SIZE CIRCUITS, THEN MA=AM

Authors
ARVIND V KOBLER J SCHONING U SCHULER R
Citation
V. Arvind et al., IF NP HAS POLYNOMIAL-SIZE CIRCUITS, THEN MA=AM, Theoretical computer science, 137(2), 1995, pp. 279-282
Citations number
13
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
137
Issue
2
Year of publication
1995
Pages
279 - 282
Database
ISI
SICI code
0304-3975(1995)137:2<279:INHPCT>2.0.ZU;2-5
Abstract
It is shown that the assumption of NP having polynomial-size circuits implies (apart from a collapse of the polynomial-time hierarchy as sho wn by Karp and Lipton) that the classes AM and MA of Babai's Arthur-Me rlin hierarchy coincide. This means that also a certain inner collapse of the remaining classes of the polynomial-time hierarchy occurs.