A Note on the Complexity of <I>k</I>-Ary Threshold Circuits

Shao-Chin SUNG; Kunihiko HIRAISHI

A Note on the Complexity of k-Ary Threshold Circuits

Shao-Chin SUNG, Kunihiko HIRAISHI

Full Text Views

0

Cite this

Summary :

Obradovic and Parberry 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ⁿ). 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^k+1). 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^n-1). 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ⁿ). 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^k-1), and can be computed by a depth 3 unit-weight k-ary threshold circuit of size O(kn^k-1). 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.

Publication: IEICE TRANSACTIONS on Information Vol.E80-D No.8 pp.767-773

Publication Date: 1997/08/25

Publicized

Online ISSN

DOI

Type of Manuscript

Category: Algorithm and Computational Complexity

Cite this

Copy

Shao-Chin SUNG, Kunihiko HIRAISHI, "A Note on the Complexity of k-Ary Threshold Circuits" in IEICE TRANSACTIONS on Information, vol. E80-D, no. 8, pp. 767-773, August 1997, doi: .
Abstract: Obradovic and Parberry 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ⁿ). 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^k+1). 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^n-1). 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ⁿ). 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^k-1), and can be computed by a depth 3 unit-weight k-ary threshold circuit of size O(kn^k-1). 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e80-d_8_767/_p

Copy

@ARTICLE{e80-d_8_767,
author={Shao-Chin SUNG, Kunihiko HIRAISHI, },
journal={IEICE TRANSACTIONS on Information},
title={A Note on the Complexity of k-Ary Threshold Circuits},
year={1997},
volume={E80-D},
number={8},
pages={767-773},
abstract={Obradovic and Parberry 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ⁿ). 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^k+1). 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^n-1). 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ⁿ). 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^k-1), and can be computed by a depth 3 unit-weight k-ary threshold circuit of size O(kn^k-1). 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.},
keywords={},
doi={},
ISSN={},
month={August},}

Copy

TY - JOUR
TI - A Note on the Complexity of k-Ary Threshold Circuits
T2 - IEICE TRANSACTIONS on Information
SP - 767
EP - 773
AU - Shao-Chin SUNG
AU - Kunihiko HIRAISHI
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E80-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 1997
AB - Obradovic and Parberry 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ⁿ). 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^k+1). 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^n-1). 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ⁿ). 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^k-1), and can be computed by a depth 3 unit-weight k-ary threshold circuit of size O(kn^k-1). 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.
ER -