Mean Computing Time of Boolean Operators by Programs with Restricted Memory / A. V. Chashkin. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2017. № 3. P. 16-21 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 102-106].

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.

Key words: Boolean operators, average computation time, computation with bounded storage.