On the average-case complexity of underdetermined functions. (English. Russian original) Zbl 1393.68070
Discrete Math. Appl. 28, No. 4, 201-221 (2018); translation from Diskretn. Mat. 29, No. 2, 133-159 (2017).
Summary: 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.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68P05 | Data structures |
| 94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |
Keywords:
underdetermined function; Boolean function; Boolean circuit; straight-line program; average-case complexityReferences:
| [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. · Zbl 0733.94026 |
| [2] | Krichevskii R. E., Information compression and search, Radio i Svyaz’, Moscow, 1989 (in Russian). |
| [3] | Lupanov O. B., “An approach to systems synthesis: A local coding principle”, Probl. Kibern., 14 (1965), 31-110 (in Russian). · Zbl 0256.94043 |
| [4] | Nechiporuk E. I., “On the topological principles of self-correction”, Probl. Kibern., 21 (1969), 5-102 (in Russian). · Zbl 0195.46602 |
| [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). · Zbl 0139.11703 |
| [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. · Zbl 0925.68334 |
| [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). · Zbl 0868.94058 |
| [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). · Zbl 0913.94029 |
| [9] | Sholomov L. A., “On functionals characterizing the complexity of systems of undetermined Boolean functions”, Probl. Kibern., 19 (1967), 123-140 (in Russian). |
| [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). · Zbl 0246.94024 |
| [11] | Sholomov L. A.“Informational properties of complexity functionals for systems of partial Boolean functions”, Probl. Kibern., 34 (1978), 133-150 (in Russian). · Zbl 0415.94018 |
| [12] | Andreev A. E., “Complexity of nondetetministic functions”, BRICS Report Series, RS-94-2. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
