Counting in Uniform TC 0
Jui-Lin Lee · 1997
. In this paper we first give a uniform AC 0 algorithm which uses partial sums to compute multiple addition. Then we use it to show that multiple addition is computable in uniform TC 0 by using count only once sequentially. By constructing bit matrix for multiple addition, we prove that multiple product with poly-logarithmic size is computable in uniform TC 0 (by using count k + 1 times sequentially when the product has size O((logn) k )). We also prove that multiple product with sharply bounded size is computable in uniform AC 0 . 1. Introduction In this paper we study basic counting techniques inside uniform TC 0 . We adopt function algebraic approach, for it requires less background and has more mathematical (or at least machine-independent) favor. The study of complexity classes related to parallel computation is nowadays more important since parallel computing is thought to be useful. In theoretical computer science there are several well-developed parallel models. We...