Name
Abstract | ||
|---|---|---|
The parallel complexity class NC1 has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. (J. Comput. Syst. Sci. 57: 200-212, 1992) considered arithmetizations of two of these classes, # NC1 and # BWBP. We further this study to include arithmetization of other classes. In particular, we show that counting paths in branching programs over visibly pushdown automata is in FLogDCFL, while counting proof-trees in logarithmic width formulae has the same power as # NC1. We also consider polynomial-degree restrictions of SCi, denoted sSC(i), and show that the Boolean class sSC(1) is sandwiched between NC1 and L, whereas sSC(0) equals NC1. On the other hand, the arithmetic class # sSC(0) contains # BWBP and is contained in FL, and # sSC(1) contains # NC1 and is in SC2. We also investigate some closure properties of the newly defined arithmetic classes. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/s00224-009-9233-3 | THEORY OF COMPUTING SYSTEMS |
Keywords | Field | DocType |
Bounded-width circuits,Branching programs,Circuit degree,Arithmetization | Discrete mathematics,Combinatorics,Mathematics | Journal |
Volume | Issue | ISSN |
46.0 | SP3 | 1432-4350 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nutan Limaye | 1 | 134 | 20.59 |
| Meena Mahajan | 2 | 688 | 56.90 |
| B. V. Raghavendra Rao | 3 | 53 | 13.86 |