|
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.
Citation:
S. V. Jenevsky, S. L. Melnikov, A. N. Shurupov, “On the recognition problem for algebraic threshold functions”, Prikl. Diskr. Mat. Suppl., 2019, no. 12, 206–211
Linking options:
https://www.mathnet.ru/eng/pdma473 https://www.mathnet.ru/eng/pdma/y2019/i12/p206
|
Statistics & downloads: |
Abstract page: | 149 | Full-text PDF : | 59 | References: | 20 |
|