Details

Autor(en) / Beteiligte

• Sergeev, I. S.

Titel

Formula Complexity of a Linear Function in a -ary Basis

Ist Teil von

• Mathematical Notes, 2021, Vol.109 (3-4), p.445-458

Ort / Verlag

Moscow: Pleiades Publishing

Erscheinungsjahr

2021

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• The Khrapchenko method of finding a lower bound for the complexity of binary formulas is extended to formulas in -ary bases. The resulting extension makes it possible to evaluate the complexity of linear Boolean functions and a majority function of variables when realized by formulas in the basis of all -ary monotone functions and negation as , where . For a linear function, the complexity bound in this form is unimprovable. For , the sharper lower bound is proved.