On the recognition problem for algebraic threshold functions | Applied Discrete Mathematics. Supplement. 2019. № 12. DOI: 10.17223/2226308X/12/58

On the recognition problem for algebraic threshold functions

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)(ⁿ+⁵)^/2/2ⁿ+² and the bound of algorithm complexity is O((n/2)ⁿ²).

Download file

Counter downloads: 108

Keywords

алгебраическая булева пороговая функция, проблема распознавания, recognition problem, algebraic threshold functions

Authors

Name	Organization	E-mail
Jenevsky S. V.	FUMO VO "Information Security"	zhenevski@yandex.ru
Melnikov S. L.	FUMO VO "Information Security"	msl23021996@mail.ru
Shurupov A.N.	FUMO VO "Information Security"	ashurupov@mail.ru

Всего: 3

References

Сошин Д. А. Конструктивный метод синтеза сбалансированных k-значных алгебраических пороговых функций // Computational Nanotechnology. 2015. No. 4. P. 31-36.

Золотых Н. Ю. Расшифровка пороговых и близких к ним пороговых функций многозначной логики: дис.. канд. физ.-мат. наук. Нижегородский госуниверситет. Н. Новгород, 1998.

Бурделев А. В., Никонов В. Г. О построении аналитического задания k-значной пороговой функции // Computational Nanotechnology. 2015. No. 2. P. 5-13.

Crama Y. and Hammer P. L. Boolean Functions: Theory, Algorithms and Applications. Encyclopedia of Mathematics and its Applications. Cambridge: Cambridge University Press, 2011.

Antony M. Discrete Mathematics of Neural Networks: Selected Topics. SIAM, Philadelphia, 2001.