Name
Abstract | ||
|---|---|---|
The class NC^1 of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we examine the structure of classes in between NC^1 and L based on counting functions or, equivalently, based on arithmetic circuits. The classes PNC^1 and C"=NC^1, defined by a test for positivity and a test for zero, respectively, of arithmetic circuit families of logarithmic depth, sit in this complexity interval. We study the landscape of Boolean hierarchies, constant-depth oracle hierarchies, and logarithmic-depth oracle hierarchies over PNC^1 and C"=NC^1. We provide complete problems, obtain the upper bound L for all these hierarchies, and prove partial hierarchy collapses. In particular, the constant-depth oracle hierarchy over PNC^1 collapses to its first level PNC^1, and the constant-depth oracle hierarchy over C"=NC^1 collapses to its second level. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.tcs.2011.05.050 | MFCS'10 Proceedings of the 35th international conference on Mathematical foundations of computer science |
Keywords | DocType | Volume |
NC1 collapse,logarithmic space,level PNC1,PNC1 collapse,NC1and L.,Boolean hierarchy,classes PNC1,fine structure,logarithmic-depth oracle hierarchy,logarithmic depth,class NC1,constant-depth oracle hierarchy | Conference | 417, |
ISSN | ISBN | Citations |
Theoretical Computer Science | 3-642-15154-X | 3 |
PageRank | References | Authors |
0.43 | 13 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samir Datta | 1 | 200 | 19.82 |
| Meena Mahajan | 2 | 688 | 56.90 |
| B. V. Raghavendra Rao | 3 | 53 | 13.86 |
| Michael Thomas | 4 | 32 | 3.22 |
| Heribert Vollmer | 5 | 805 | 71.64 |