ECCC-Report TR01-048https://eccc.weizmann.ac.il/report/2001/048Comments and Revisions published for TR01-048en-usTue, 10 Jul 2001 19:43:26 +0300
Paper TR01-048
| Branching program, commutator, and icosahedron, part I |
Jui-Lin Lee
https://eccc.weizmann.ac.il/report/2001/048In this paper we give a direct proof of $N_0=N_0^\prime$, i.e., the equivalence of
uniform $NC^1$ based on different recursion principles: one is OR-AND complete
binary tree (in depth $\log n$) and the other is the recursion on notation with value
bounded in $[0,k]$ and $|x|(=n)$ many steps. A byproduct is that the multiple product
of $p(\log n)$ many Boolean matrices with size $q(\log n)\times q(\log n)$ (where
$p,q$ are polynomials and $n$ is the input size) is computable in uniform $NC^1$.
We also investigate the computational power of $LR(f),RL(f),DC(f)$ according to the
associativity and commutativity of $f$ and the size of $B$.
Tue, 10 Jul 2001 19:43:26 +0300https://eccc.weizmann.ac.il/report/2001/048