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/

[1] Andreev A. E., “On the complexity of realization of partial Boolean functions by circuits of functional elements”, Discrete Math. Appl., 1:3 (1991), 251–261 | DOI | MR | Zbl | Zbl

[2] Krichevskii R. E., Szhatie i poisk informatsii, Radio i svyaz, M., 1989 | MR

[3] Lupanov O. B., “Ob odnom podkhode k sintezu upravlyayuschikh sistem — printsipe lokalnogo kodirovaniya”, Problemy kibernetiki, 14 (1965), 31–110 | MR | Zbl

[4] Nechiporuk E. I., “O topologicheskikh printsipakh samokorrektirovaniya”, Problemy kibernetiki, 21 (1969), 5–102 | MR | Zbl

[5] Nechiporuk E. I., “O slozhnosti ventilnykh skhem, realizuyuschikh bulevskie matritsy s neopredelennymi elementami”, Doklady AN SSSR, 163:1, 40–42 | MR

[6] Chashkin A. V., “On the complexity of Boolean matrices, graphs, and the Boolean functions corresponding to them”, Discrete Math. Appl., 4:3 (1994), 229–257 | DOI | MR | Zbl

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

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

[9] Sholomov L. A., “O funktsionalakh, kharakterizuyuschikh slozhnost sistem nedoopredelennykh bulevykh funktsii”, Problemy kibernetiki, 19 (1967), 123–140

[10] Sholomov L. A., “O realizatsii nedoopredelennykh bulevykh funktsii skhemami iz funktsionalnykh elementov”, Problemy kibernetiki, 21 (1969), 215–226

[11] Sholomov L. A., “Informatsionnye svoistva funktsionalov slozhnosti dlya sistem nedoopredelennykh bulevykh funktsii”, Problemy kibernetiki, 34 (1978), 133–150 | Zbl

[12] Andreev A. E., “Complexity of nondetetministic functions”, BRICS Report Series, RS-94-2