Abstract
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.
Funding
This work was supported by the Russian Foundation for Basic Research, project no. 14-01-00598.
Originally published in Diskretnaya Matematika (2017) 29, №2, 133–159 (in Russian).
References
[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.10.1515/dma.1991.1.3.251Search in Google Scholar
[2] Krichevskii R. E., Information compression and search, Radio i Svyaz’, Moscow, 1989 (in Russian).Search in Google Scholar
[3] Lupanov O. B., “An approach to systems synthesis: A local coding principle”, Probl. Kibern., 14 (1965), 31–110 (in Russian).Search in Google Scholar
[4] Nechiporuk E. I., “On the topological principles of self-correction”, Probl. Kibern., 21 (1969), 5–102 (in Russian).Search in Google Scholar
[5] Nechiporuk E. I., “Complexity of gating circuits realized by Boolean matrices with undetermined elements”, Doklady Akademii Nauk SSSR, 1965:1, 40–42 (in Russian).Search in Google Scholar
[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.10.1515/dma.1994.4.3.229Search in Google Scholar
[7] Chashkin A. V., “On the average time for the computation of the values of Boolean functions Boolean functions”, Diskretn. Anal. Issled. Oper., Ser. 1, 4:1 (1997), 60–78 (in Russian).Search in Google Scholar
[8] Chashkin A. V., “On the mean time for computing Boolean operators”, Diskretn. Anal. Issled. Oper., Ser. 1, 5:1 (1998), 88–103 (in Russian).Search in Google Scholar
[9] Sholomov L. A., “On functionals characterizing the complexity of systems of undetermined Boolean functions”, Probl. Kibern., 19 (1967), 123–140 (in Russian).Search in Google Scholar
[10] Sholomov L. A., “On the realization of not completely defined Boolean functions by circuits of functional elements”, Probl. Kibern., 21 (1969), 215–226 (in Russian).Search in Google Scholar
[11] Sholomov L. A.“Informational properties of complexity functionals for systems of partial Boolean functions”, Probl. Kibern., 34 (1978), 133–150 (in Russian).Search in Google Scholar
[12] Andreev A. E., “Complexity of nondetetministic functions”, BRICS Report Series, RS-94-2.Search in Google Scholar
© 2018 Walter de Gruyter GmbH, Berlin/Boston
