RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2009 Volume 16, Issue 5, Pages 78–87 (Mi da589)

This article is cited in 4 papers

On the complexity of generalized contact circuits

K. L. Rychkov

S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia

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.

UDC: 519.174

Received: 05.06.2009



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024