RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2008 Volume 20, Issue 1, Pages 120–130 (Mi dm995)

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.

UDC: 519.7

Received: 19.12.2005

DOI: 10.4213/dm995


 English version:
Discrete Mathematics and Applications, 2008, 18:2, 131–142

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024