|
This article is cited in 2 scientific papers (total in 2 papers)
On the average-case complexity of underdetermined functions
A. V. Chashkin Lomonosov Moscow State University
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.
Keywords:
underdetermined function, Boolean function, Boolean circuit, straight-line program, average-case complexity.
Received: 16.01.2017
Citation:
A. V. Chashkin, “On the average-case complexity of underdetermined functions”, Diskr. Mat., 29:2 (2017), 133–159; Discrete Math. Appl., 28:3 (2018), 201–221
Linking options:
https://www.mathnet.ru/eng/dm1434https://doi.org/10.4213/dm1434 https://www.mathnet.ru/eng/dm/v29/i2/p133
|
Statistics & downloads: |
Abstract page: | 337 | Full-text PDF : | 52 | References: | 48 | First page: | 28 |
|