О проблеме распознавания алгебраических пороговых функций | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/58

О проблеме распознавания алгебраических пороговых функций

Доказано существование переборного алгоритма распознавания алгебраических булевых пороговых функций путём нахождения верхних оценок абсолютных значений модуля и коэффициентов линейной формы. Оценка для модуля имеет вид (n + 3)(n+5)/2/2n+2, а сложность алгоритма - O((n/2)п).

On the recognition problem for algebraic threshold functions.pdf Интерес к алгебраическим булевым пороговым функциям обуславливается простотой их задания, а также тем, что класс алгебраических пороговых функций содержит как собственно пороговые (или линейные пороговые) булевы функции, так и линейные булевы функции. Впервые понятие и свойства алгебраических пороговых функций (булевых и многозначных) введено в [1]. Несмотря на то, что понятие алгебраической булевой пороговой функции близко к понятию булевой пороговой функции, проблема распознавания для алгебраических булевых пороговых функций пока не имеет таких ясных способов решения, которые известны для булевых пороговых функций [2]. В работе доказано существование переборного алгоритма путем нахождения верхних оценок абсолютных значений модуля и коэффициентов линейной формы. Будем использовать следующие обозначения: Qk = {0,1,... ,k - 1}; rm(a) -функция взятия остатка при делении целого числа a на m; Fk (n) -множество всех k-значных функций от n переменных; Tk (n) - класс всех k-значных пороговых функций от n переменных; ATk (n) - класс всех k-значных алгебраических пороговых функций от n переменных; Lk (n) -множество всех линейных функций k-значной логики от n переменных вида c0 + c1x1 + c2x2 + ... + cnxn (mod k). Определение 1. Функцию f : ^П -> П2 назовем алгебраической булевой пороговой (а.б.п.ф.), если существуют ш = (ш0,ш1,... ,шп) Е Zn+1, в Е Z, m Е N\\{1}, такие, что f (Х1, . . . ,Хп) = 0 ^ Гт(шо + Ш1Х1 + Ш2Х2 + ... + ШпХп)

Ключевые слова

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

Авторы

ФИООрганизацияДополнительноE-mail
Женевский Степан ВикторовичФУМО ВО «Информационная безопасность»сотрудникzhenevski@yandex.ru
Мельников Сергей ЛеонидовичФУМО ВО «Информационная безопасность»сотрудникmsl23021996@mail.ru
Шурупов А.Н.ФУМО ВО «Информационная безопасность»кандидат технических наук, доцент, сотрудникashurupov@mail.ru
Всего: 3

Ссылки

Сошин Д. А. Конструктивный метод синтеза сбалансированных 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.
 О проблеме распознавания алгебраических пороговых функций | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/58

О проблеме распознавания алгебраических пороговых функций | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/58