Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-048 | 3rd June 2001 00:00

Branching program, commutator, and icosahedron, part I

RSS-Feed




TR01-048
Authors: Jui-Lin Lee
Publication: 10th July 2001 19:43
Downloads: 3351
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