About the potential for the ellipsoid method application to the threshold function recognition
For solving the decision problem about whether a Boolean function is threshold, the ellipsoid method is proposed to use. A polynomial complexity of the algorithm developed for this method by L. G. Khachiyan allows to expect that the computing complexity of the decision problem just mentioned is also polynomial.
Download file
Counter downloads: 157
Keywords
пороговые функции, метод эллипсоидов, алгоритм Хачияна, threshold function, ellipsoid method, Khachiyan's algorithmAuthors
| Name | Organization | |
| Lapikov I. I. | Research Institute "KVANT" | Lapikov.I.I@yandex.ru |
References
Хачиян Л. Г. Полиномиальные алгоритмы в линейном программировании // ЖВМиМФ. 1980. Вып. 20. №1. С. 51-68.
Зуев А. Ю. Пороговые функции и пороговые представления булевых функций // Математические вопросы кибернетики. 1994. №5. С. 5-61.
Никонов В. Г. Пороговые представления булевых функций // Обозрение прикл. и промышл. математики. 1994. Вып. 1. №3. С. 458-545.
Кудрявцев Л. Г. Теория тестового распознавания // Дискретная математика. 2006. Вып. 18. №3. С. 3-34.
Бурделев А. В., Никонов В. Г., Лапиков И. И. Распознавание параметров узла защиты информации, реализованного пороговой k-значной функцией // Труды СПИИРАН. 2016. Вып. 46. С. 108-127.
Дертоузос П. Пороговая логика. М.: Мир, 1967. 344 с.
Лапиков И. И., Никонов В. Г. Адаптивный алгоритм решения систем неравенств с k-значными неизвестными // Труды Военно-космической академии им. А. Ф. Можайского. 2016. Вып.1. С. 88-94.
