Aleksandr V. Chashkin

The paper about the Chair of Discrete Mathematics of the Faculty of Mechanics and Mathematics of Lomonosov Moscow State University discusses the issues of

The average-case complexity of computing monotone Boolean functions by straight-line programs without memory with a conditional stop in the basis of all Bo

Given a binomial probability distribution on the n-dimensional Boolean cube, the complexity of implementation of Boolean functions by straight line programs with conditional stop is considered. The order, as n → ∞, of the average-case complexity of almost all n-place Boolean functions is established.

The average-case complexity of computation of underdetermined functions by straight-line programs with conditional stop over the basis of all at most two-place Boolean functions is considered. Correct order estimates of the average-case complexity of functions with maximum average-case complexity among all underdetermined functions are derived depending on the degree of their determinacy, the size of their domain, and the size of their support.

The number of incomparable k-dimensional intervals in the Boolean n-cube is estimated. The result is used to estimate the complexity of approximate computation of an arbitrary monotone Boolean functio

We consider average-case complexity of computing monotone Boolean functions by straight-line programs with a conditional stop over the basis of all Boolean functions of at most two variables. For the set of all n -ary monotone Boolean functions new Shannon-type upper and lower bounds for the average-case complexity as n → ∞ are established.

The mean computing time for computation of values of Boolean operators by straight-line programs with a conditional stop and the storage of at most D is studied. An asymptotically exact formula for the mean computation time is obtained for growing number n of variables and for almost all Boolean operators with m components in a wide range of D and m.