Geodesic
Bounds for the average-case complexity of monotone Boolean functions
Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 146-153
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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\to\infty$ are established.
Keywords: monotone Boolean functions, average-case complexity. 
@article{DM_2016_28_2_a13,
     author = {A. V. Chashkin},
     title = {Bounds for the average-case complexity of monotone {Boolean} functions},
     journal = {Diskretnaya Matematika},
     pages = {146--153},
     year = {2016},
     volume = {28},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_2_a13/}
}
TY  - JOUR
AU  - A. V. Chashkin
TI  - Bounds for the average-case complexity of monotone Boolean functions
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 146
EP  - 153
VL  - 28
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_2_a13/
LA  - ru
ID  - DM_2016_28_2_a13
ER  - 
%0 Journal Article
%A A. V. Chashkin
%T Bounds for the average-case complexity of monotone Boolean functions
%J Diskretnaya Matematika
%D 2016
%P 146-153
%V 28
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2016_28_2_a13/
%G ru
%F DM_2016_28_2_a13
A. V. Chashkin. Bounds for the average-case complexity of monotone Boolean functions. Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 146-153. http://geodesic.mathdoc.fr/item/DM_2016_28_2_a13/

[1] Zabaluev R. N., “On the mean complexity of monotone functions”, Discrete Math. Appl., 16:2 (2006), 181–194 | DOI | DOI | MR | Zbl

[2] Ugolnikov A. B., “O realizatsii monotonnykh funktsii skhemami iz funktsionalnykh elementov”, Problemy kibernetiki, 1976, no. 31, 167–185, M.: Nauka | MR

[3] Chashkin A. V., “O srednem vremeni vychisleniya znachenii bulevykh funktsii”, Diskretnyi analiz i issledovanie operatsii, 4:1 (1997), 60–78 | MR | Zbl

[4] Chashkin A. V., “O srednem vremeni vychisleniya bulevykh operatorov”, Diskretnyi analiz i issledovanie operatsii, 5:1 (1998), 88–103 | MR | Zbl