Name
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. Thismeans that also a certain inner collapse of the remaining classes of the polynomialtimehierarchy occurs.It is well known [KL80] that the assumption of NP having polynomial-size circuits(in symbols NP ` P=poly) implies that the polynomial-time hierarchy... |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0304-3975(95)91133-B | Theoretical Computer Science |
Keywords | DocType | Volume |
polynomial-size circuit | Journal | 137 |
Issue | ISSN | Citations |
2 | Theoretical Computer Science | 9 |
PageRank | References | Authors |
0.62 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vikraman Arvind | 1 | 296 | 38.18 |
| Johannes Köbler | 2 | 580 | 46.51 |
| Uwe Schöning | 3 | 998 | 105.69 |
| Rainer Schuler | 4 | 9 | 0.62 |