__
TR01-048 | 3rd June 2001 00:00
__

#### Branching program, commutator, and icosahedron, part I

**Abstract:**
In 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$.