Vol 71, No 3 (2016)

The paper discusses the asymptotic depth of a reversible circuits consisting of NOT, CNOT and 2-CNOT gates. The reversible circuit depth function D(n, q) is introduced for a circuit implementing a mapping f: Z₂ⁿ → Z₂ⁿ as a function of n and the number q of additional inputs. It is proved that for the case of implementation of a permutation from A(Z₂ⁿ) with a reversible circuit having no additional inputs the depth is bounded as D(n, 0) ≳ 2ⁿ/(3log₂n). It is also proved that for the case of transformation f: Z₂ⁿ → Z₂ⁿ with a reversible circuit having q₀ ~ 2ⁿ additional inputs the depth is bounded as D(n,q₀) ≲ 3n.

The relationship of multidimensional geometry with statistical thermodynamics and with laws of large numbers is described.

A single server queueing system with an unreliable server and priority customers is considered. The limit distribution of the number of ordinary customers in the system is obtained.

The topology of the space of closures of solutions to an integrable system on the Lie algebra so(4) being an analogue of the Kovalevskaya case has been studied. Fomenko-Zieschang invariants are calculated for this purpose in the case of zero area integral, which classify isoenergetic 3-surfaces and the corresponding Liouville foliations.

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₀.