|
On complexity of realisation of a class of almost symmetric functions by formulas of depth 3
S. E. Cherukhina
Abstract:
We consider the class of almost symmetric Boolean functions. For any function of this class, the values on all tiers except the second one coincide with the values of a monotone symmetric function with threshold 3. The values on the second tier are arbitrary. We study realisation of functions of this class by $\&\vee\&$- formulas over the basis $\{\&,\vee\}$.
We obtain a sharp bound for the minimum complexity of the functions of this class (the function of minimum complexity is explicitly written out) and an asymptotic estimate of complexity of a monotone symmetric function with threshold 3 which is maximal in order of complexity in the class under consideration.
Received: 19.12.2005
Citation:
S. E. Cherukhina, “On complexity of realisation of a class of almost symmetric functions by formulas of depth 3”, Diskr. Mat., 20:1 (2008), 120–130; Discrete Math. Appl., 18:2 (2008), 131–142
Linking options:
https://www.mathnet.ru/eng/dm995https://doi.org/10.4213/dm995 https://www.mathnet.ru/eng/dm/v20/i1/p120
|
Statistics & downloads: |
Abstract page: | 362 | Full-text PDF : | 166 | References: | 28 | First page: | 2 |
|