Volume 16, No 5, 2009, P. 78-87

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 parallel-serial 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 two-valued (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,q-1\}^n\to\{0,1\}$ which accepts the value 1 at a vector $(\delta_1,\dots,\delta_n)\in\{0,1,\dots,q-1\}^n$ if $\delta_1+\dots+\delta_n\neq0\pmod q$.
Bibl. 9.

Keywords: Boolean function, contact circuit, complexity of circuits.

Rychkov Konstantin Leonidovich ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: rychkov@math.nsc.ru