Volume 16, No 5, 2009, P. 7887
UDC 519.714
K. L. Rychkov
On the complexity of generalized contact circuits
Abstract:
We consider generalizations of the concepts of a contact circuit and a parallelserial contact circuit in the case when the variables assigned to contacts can accept not two as in a Boolean case, but a greater number of values. The conductivity of contacts as well as in a Boolean case remains twovalued (a contact either will close, or will break). We have obtained upper and lower bounds on the complexity of such circuits computing a function $f\colon\{0,1,\dots,q1\}^n\to\{0,1\}$ which accepts the value 1 at a vector $(\delta_1,\dots,\delta_n)\in\{0,1,\dots,q1\}^n$ if $\delta_1+\dots+\delta_n\neq0\pmod q$.
Bibl. 9.
Keywords: Boolean function, contact circuit, complexity of circuits.
Rychkov Konstantin Leonidovich ^{1}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
email: rychkov@math.nsc.ru
