Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR01-048 | 3rd June 2001 00:00

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

TR01-048
Authors: Jui-Lin Lee
Publication: 10th July 2001 19:43
Keywords:

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$.

ISSN 1433-8092 | Imprint