On Complexity of Oriented Contact Circuits with Limited Out-degree

A. E. Shiganov

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 151 (2009) no. 2, pp. 164-172

Résumé

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)$.

Détail

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