RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2019 Issue 12, Pages 206–211 (Mi pdma473)

Computational methods in discrete mathematics

On the recognition problem for algebraic threshold functions

S. V. Jenevsky, S. L. Melnikov, A. N. Shurupov

ФУМО ВО «Информационная безопасность», г. Москва

Abstract: We prove the existence of recognition algorithm for algebraic Boolean threshold functions by calculating upper bounds of absolute values of modulo and coefficients of a linear form. The modulo bound looks like $(n+3)^{(n+5)/2}/2^{n+2}$ and the bound of algorithm complexity is O$(({{n}/{2}})^{n^2})$.

Keywords: recognition problem, algebraic threshold functions.

UDC: 512.55

DOI: 10.17223/2226308X/12/58



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024