The XV International Conference "Problems of Theoretical Cybernetics"

On Complexity of Oriented Contact Circuits with Limited Out-degree

A. E. Shiganov

M. V. Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics

Abstract: The paper studies the implementation of Boolean functions in the class of oriented contact circuits with some restriction on the weight and number of adjacent contacts. Circuits under consideration are those in which out-degree of every vertex is not more than $\lambda$. The weight of vertex is defined as $\lambda$ if its in-degree is one and $\lambda(1+\omega)$, where $\omega>0$, otherwise. Weight of the circuit is sum of weights of its vertices. Weight of Boolean function $f$ is defined as minimal weight of circuit implementing $f$. Shannon function $W_{\lambda,\omega}(n)$ is maximal weight of Boolean function on $n$ input variables. For this function in case when $\lambda>1$ and for any $\omega>0$ we obtain so-called high-accuracy asymptotic bound:
$$ W_{\lambda,\omega}(n)=\frac\lambda{\lambda-1}\frac{2^n}n\Biggl(1+\frac{\frac{\lambda-2}{\lambda-1}\log n\pm O(1)}n\Biggr). $$

The results shows how introduction of restrictions on the out-degree of circuit's vertices influences asymptotic behaviour of Shannon function $W_{\lambda,\omega}(n)$ and term $\log n/n$ in its asymptotic expansion. Note that value of $\omega$ influences only on constant in the term $O(1)$.

Keywords: Boolean function, oriented contact circuit, complexity, Shannon function, high-accuracy asymptotic bound.

UDC: 519.95

Received: 02.03.2009