Geodesic
On the average-case complexity of underdetermined functions
Diskretnaya Matematika, Tome 29 (2017) no. 2, pp. 133-159

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: underdetermined function, Boolean function, Boolean circuit, straight-line program, average-case complexity. 
@article{DM_2017_29_2_a9,
     author = {A. V. Chashkin},
     title = {On the average-case complexity of underdetermined functions},
     journal = {Diskretnaya Matematika},
     pages = {133--159},
     publisher = {mathdoc},
     volume = {29},
     number = {2},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2017_29_2_a9/}
}
TY  - JOUR
AU  - A. V. Chashkin
TI  - On the average-case complexity of underdetermined functions
JO  - Diskretnaya Matematika
PY  - 2017
SP  - 133
EP  - 159
VL  - 29
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2017_29_2_a9/
LA  - ru
ID  - DM_2017_29_2_a9
ER  - 
%0 Journal Article
%A A. V. Chashkin
%T On the average-case complexity of underdetermined functions
%J Diskretnaya Matematika
%D 2017
%P 133-159
%V 29
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2017_29_2_a9/
%G ru
%F DM_2017_29_2_a9
A. V. Chashkin. On the average-case complexity of underdetermined functions. Diskretnaya Matematika, Tome 29 (2017) no. 2, pp. 133-159. http://geodesic.mathdoc.fr/item/DM_2017_29_2_a9/