The conjunction complexity asymptotic of self-correcting circuits for monotone symmetric functions with threshold 2
T. I. Krasnova · Moscow University Mathematics Bulletin · 2014
It is shown that the conjunction complexity L & (f 2 ) of monotone symmetric Boolean functions $$f_2^n (x_1 , \ldots ,x_n ) = \mathop \vee \limits_{1 \leqslant i < j \leqslant n} x_i x_j$$ realized by k-self-correcting circuits in the basis B = {&, −} asymptotically equals to (k + 2)n for growing n providing the price of a reliable conjunctor is ≥ k + 2.