Complexity lower bound for Boolean functions in the class of extended operator forms

DOI10.26516/1997-7670.2019.30.125zbMath1460.94099OpenAlexW2997867077MaRDI QIDQ2306843

Aleksandr Sergeevich Balyuk

Publication date: 26 March 2020

Published in: Izvestiya Irkutskogo Gosudarstvennogo Universiteta. Seriya Matematika (Search for Journal in Brave)

Full work available at URL: http://mathizv.isu.ru/en/article/file?id=1325

zbMATH Keywords

lower boundBoolean functionMersenne primeextension of finite field

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30) Boolean functions (94D10)

Related Items

On decompositions of decision function quality measure, On length of Boolean functions of a small number of variables in the class of pseudo-polynomials

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials
• Complexity of Boolean functions in the class of polarized polynomial forms
• Lower bounds of complexity for polarized polynomials over finite fields
• Upper bound for the length of functions over a finite field in the class of pseudopolynomials
• Complexity of Boolean functions' representations in classes of extended pair-generated operator forms