Inversion complexity of self-correcting circuits for a certain sequence of boolean functions

The asymptotics L _k ^? (f ₂ ⁿ ) ?? n min{k+1, p} is obtained for the sequence of Boolean functions $f_2^n \left( {x_1 , \ldots ,x_n } \right) = \mathop \vee \limits_{1 \leqslant i < j \leqslant n}$ for any fixed k, p ?? 1 and growing n, here L _k ^? (f ₂ ⁿ ) is the inversion complexity of realization of the function f ₂ ⁿ by k-self-correcting circuits of functional elements in the basis B = {&, ?}, p is the weight of a reliable invertor.     

Complexity of sequential computations of partial Boolean functions by circuits

A pair (f, g) of partial Boolean functions is characterized by a tuple of parameters l _αβ that is the number of tuples $ \tilde x A pair (f, g) of partial Boolean functions is characterized by a tuple of parameters l _αβ that is the number of tuples such that (f( ), g( )) = (α, β), where α and β take the values 0, 1, and an undefined value. The sequential computation of (f, g) is considered when a circuit S _f for f is constructed first, and, next, it is completed by the construction up to a circuit S _f,g . It is shown that if the domain D(f) includes D(g) then it is possible to compute sequentially f and g in such a way that S _f and S _f,g are asymptotically minimal simultaneously (i.e., they satisfy the asymptotically best bounds on the complexity for corresponding classes); and, in general, these functions cannot be sequentially computed in the order g, f so that S _g and S _f,g are asymptotically minimal. An attainable lower bound is obtained on the size of the circuit S _f,g for the sequential computation. The information properties of partially defined data play an essential role whose study in the previous papers of the author is continued here. Original Russian Text ? L.A. Sholomov, 2007, published in Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1, 2007, Vol. 14, No. 1, pp. 110–139.     

Complexity and depth of formulas for symmetric Boolean functions

A new approach for implementation of the counting function for a Boolean set is proposed. The approach is based on approximate calculation of sums. Using this approach, new upper bounds for the size and depth of symmetric functions over the basis B₂ of all dyadic functions and over the standard basis B₀ = {∧, ∨,^- } were non-constructively obtained. In particular, the depth of multiplication of n-bit binary numbers is asymptotically estimated from above by 4.02 log₂n relative to the basis B₂ and by 5.14log₂n relative to the basis B₀.     

Complexity of realization of Boolean functions with small number of unit values by selfcorrecting contact circuits

An asymptotics for the complexity of realization of Boolean functions taking the unit value on a comparatively small set of collections of variables by self-correcting contact circuits is obtained.     

The conjunction complexity asymptotic of self-correcting circuits for monotone symmetric functions with threshold 2

It is shown that the conjunction complexity L _k ^& (f ₂ ⁿ ) of monotone symmetric Boolean functions \(f_2^n (x_1 , \ldots ,x_n ) = \mathop \vee \limits_{1 \leqslant i < j \leqslant n} x_i x_j\) realized by k-self-correcting circuits in the basis B = {&, ?} asymptotically equals to (k + 2)n for growing n providing the price of a reliable conjunctor is ≥ k + 2.     

Complexity of implementation of Boolean functions by real formulas

Upper complexity estimates are proved for implementation of Boolean functions by formulas in bases consisting of a finite number of continuous real functions and a continuum of constants. For some bases upper complexity estimates coincide with lower ones.     

Asymptotically minimal schemes for one sequence of Boolean functions

Monotone symmetric Boolean functions $ f_2^n (\tilde x) = \mathop \vee \limits_{1 \leqslant i < j \leqslant n} x_i x_j $ f_2^n (\tilde x) = \mathop \vee \limits_{1 \leqslant i < j \leqslant n} x_i x_j are considered. For such functions, the asymptotics L ^B (f ₂ ⁿ ) ∼ 3n, where L ^B (f ₂ ⁿ ) is the complexity of realization of function f ₂ ⁿ by schemes of functional elements in the basis B = {&, −}, is established.     

Complexity and structure of near-minimal contact circuits for elementary symmetric functions

The paper studies the problem of the synthesis of contact circuits for elementary symmetric functions. The structure of minimal contact circuits realizing elementary symmetric functions is established and the estimates of the complexity of the obtained circuits, which are accurate to within an additive constant, are determined. It is proved that, for substantially large n, the complexity of an elementary symmetric function of n variables with the working number w satisfies the relation L(s _n ^w ) = (2w + 1)n ? B _w , whereB _w is a nonnegative constant.     

Complexity of Boolean functions in the class of polarized polynomial forms

It is proved that values of Shannon functions in the class of polarized polynomial forms (generalized Reed-Muller forms) coincide for classes of all Boolean functions and all symmetric Boolean functions; a formula computing estimates for these functions is derived. Translated fromAlgebra i Logika, Vol. 34, No. 3, pp. 323-326, May-June, 1995.     

Realization of Boolean functions by combinational circuits embedded in the hypercube

In recent years, it has become popular to realize Boolean functions by combinational circuits. In many cases, the further use of the scheme constructed requires its geometric realization, i.e., a certain embedding in one or another specific geometric structure. The role of such structure is often played by the unit n-dimensional cube.In this paper, we consider quasihomeomorphic embeddings of combinational circuits in hypercubes such that the nodes of the scheme go into vertices of the hypercube and bundles of arcs go into similar bundles or the so-called transition trees of the hypercube having no common internal vertices.

Let B be a finite complete basis of functional elements and R _B(n) be the minimum dimension of a hypercube such that, for any function f(x ₁, …, x _n ) of Boolean logic, there is a certain scheme of functional elements in basis B realizing f(x ₁, …, x _n ) which can be quasihomeomorphically embedded in this cube. The main result of this work consists in derivation of the following estimates:

$n - \log \log (n) - c_B \leqslant R_B (n) \leqslant n - \log \log (n) + c'_B .$

Here, c _B and c′_B are basis-dependent constants.     

Complexity of realization of Boolean functions from some classes related to finite grammars by formulas of alternation depth 3

The realization complexity of Boolean functions associated with finite grammars in the class of formulas of alternation depth 3 is studied. High accuracy asymptotic bounds are obtained for the corresponding Shannon function.     

Depth of Boolean functions realized by circuits over an arbitrary infinite basis

Bounds for the circuit depth of all Boolean functions tight up to a small additive constant are obtained for all infinite bases.     

The depth of Boolean functions realized by circuits over an arbitrary basis

Realization of Boolean functions by circuits of functional elements is considered over arbitrary complete bases (including infinite ones). The depth of a circuit means the maximal number of functional elements forming an oriented chain going from inputs of the circuit to its output. It is shown that for any basis B the growth order of the Shannon function of depth D _B (n) for n → ∞ is equal to 1, log₂ n, or n, and the latter case appears if and only if the basis B is finite.     

Complexity of gene circuits,Pfaffian functions and the morphogenesis problem

We consider a model of gene circuits. We show that these circuits are capable to generate any spatio–temporal patterns. We give lower bounds on the number of genes required to create a given pattern. To cite this article: S. Vakulenko, D. Grigoriev, C. R. Acad. Sci. Paris, Ser. I 337 (2003).     

Length of diagnostic tests for Boolean circuits

Mathematical Notes -     

Complexity of functions from some classes of three-valued logic

The problem of the realization complexity for functions of the three-valued logic taking values from the set {0, 1} by formulas over incomplete generating systems is considered. Upper and lower asymptotic estimates for the corresponding Shannon functions are obtained.