A Note on the Complexity of k-Ary Threshold Circuits

概要

論文の詳細を見る
Obradovic and Parberry[3] showed that any n-input k-ary function can be computed by a depth 4 unit-weight k-ary threshold circuit of size O(nk^n). They also showed that any n-input k-ary symmetric function can be computed by a depth 6 unit-weight k-ary threshold circuit of size O(n^ltk+1gt). In this paper, we improve upon and expand their results. The k-ary threshold circuits of nonunit weight and unit weight are considered. We show that any n-input k-ary function can be computed by a depth 2 k-ary threshold circuit of size O(k^ltn-1gt). This means that depth 2 is optimal for computing some k-ary functions (e.g., a PARITY function). We also show that any n-input k-ary function can be computed by a depth 3 unit-weight k-ary threshold circuit of size O(k^n). Next, we show that any n-input k-ary symmetric function can be computed by a depth 3 k-ary threshold circuit of size O(n^ltk-1gt), and can be computed by a depth 3 unit-weight k-ary threshold circuit of size O(kn^ltk-1gt). Finally, we show that if the weights of the circuit are polynomially bounded, some k-ary symmetric functions cannot be computed by any depth 2 k-ary threshold circuit of polynomial-size.
1997-08-25