Name
Abstract | ||
|---|---|---|
We provide a uniform framework for proving the collapse of the hierarchy NC1 (C) for an exact arithmetic class C of polynomial degree. These hierarchies collapse all the way down to the third level of the AC(0)-hierarchy, AC(3)(0)(C). Our main collapsing exhibits are the classes C is an element of {C=NC1,C=L, C(=)SAC(1), C=P}. NC1 (C=L) and NC1 (C=P) are already known to collapse [1,19,20]. We reiterate that our contribution is a framework that works for all these hierarchies. Our proof generalizes a proof from [9] where it is used to prove the collapse of the AC(0) (C (=) NC1) hierarchy. It is essentially based on a polynomial degree characterization of each of the base classes. |
Year | Venue | DocType |
|---|---|---|
2014 | ALGORITHMS AND COMPUTATION, WALCOM 2014 | Conference |
Volume | ISSN | Citations |
8344 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 13 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikhil Balaji | 1 | 9 | 4.24 |
| Samir Datta | 2 | 9 | 1.21 |