|
This article is cited in 3 scientific papers (total in 3 papers)
On the mean time for computing the values of elementary Boolean functions
A. V. Chashkin
Abstract:
The disjunction, conjunction, and linear function, each depending on an increasing number of arguments, are computed by straight-line programs with a conditional stop. Asymptotically exact formulas for the average-case complexity of these functions are found. It is shown that the average-case complexities of disjunction and
conjunction are constants and the average-case complexity of the linear function coincides with its circuit size.
The research was supported by the Russian Foundation for Basic Research, grant 99-01-01175, and the Federal Program 'Integration', grant 473.
Received: 14.07.2000
Citation:
A. V. Chashkin, “On the mean time for computing the values of elementary Boolean functions”, Diskr. Mat., 12:4 (2000), 109–120; Discrete Math. Appl., 11:1 (2001), 71–81
Linking options:
https://www.mathnet.ru/eng/dm348https://doi.org/10.4213/dm348 https://www.mathnet.ru/eng/dm/v12/i4/p109
|
Statistics & downloads: |
Abstract page: | 516 | Full-text PDF : | 274 | References: | 50 | First page: | 1 |
|