рус eng
«ИЗВЕСТИЯ ИРКУТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА». СЕРИЯ «МАТЕМАТИКА»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

Список выпусков > Серия «Математика». 2024. Том 49

Вогнутые продолжения булевых функций и некоторые их свойства и приложения

Автор(ы)
Д. Н. Баротов1

1Финансовый университет при Правительстве Российской Федерации, Москва, Российская Федерация

Аннотация
Доказывается, что для любой булевой функции от n переменных существует бесконечно много функций, каждая из которых является её вогнутым продолжением на n-мерный единичный куб. Для произвольной булевой функции от n переменных построена вогнутая функция, являющаяся минимумом среди всех её вогнутых продолжений на n-мерный единичный куб. Доказано, что эта вогнутая функция на n-мерном единичном кубе непрерывна и единственна. Благодаря полученным результатам, в частности, конструктивно доказано, что задача решения системы булевых уравнений может быть сведена к задаче численной максимизации целевой функции, любой локальный максимум которой в искомой области является глобальным максимумом, тем самым проблема локальных максимумов для таких задач полностью решена.
Об авторах
Баротов Достонжон Нумонжонович, ст. преподаватель, Финансовый университет при Правительстве Российской Федерации, Москва, 109456, Российская Федерация, DNBarotov@fa.ru
Ссылка для цитирования
Баротов Д. Н. Вогнутые продолжения булевых функций и некоторые их свойства и приложения // Известия Иркутского государственного университета. Серия Математика. 2024. Т. 49. C. 105–123. https://doi.org/10.26516/1997-7670.2024.49.105
Ключевые слова
вогнутое продолжение булевой функции, булева функция, вогнутая функция, глобальная оптимизация, локальный экстремум
УДК
512.563+519.853.3
MSC
06E30, 90C25, 46N10
DOI
https://doi.org/10.26516/1997-7670.2024.49.105
Литература
  1. Баротов Д. Н. Выпуклое продолжение булевой функции и его приложения // Дискретный анализ и исследование операций. 2024. Т. 31, № 1. С. 5–18. (Принята в печать)
  2. Баротов Д. Н. О существовании и свойствах выпуклых продолжений булевых функций // Математические заметки. 2024. Т. 115, № 4. С. 533–551. (Принята в печать)
  3. Баротов Д. Н., Баротов Р. Н. Полилинейные продолжения некоторых дискретных функций и алгоритм их нахождения // Вычислительные методы и программирование. 2023. Т. 24. С. 10–23. https://doi.org/10.26089/NumMet.v24r102
  4. Баротов Д. Н., Музафаров Д. З., Баротов Р. Н. Об одном методе решения систем булевых алгебраических уравнений // Современная математика и концепции инновационного математического образования. 2021. Т. 8, № 1. С. 17—23.
  5. Файзуллин Р. Т., Дулькейт В. И., Огородников Ю. Ю. Гибридный метод поиска приближенного решения задачи 3-выполнимость, ассоциированной с задачей факторизации // Труды Института математики и механики УрО РАН. 2013. Т. 19, № 2. С. 285–294.
  6. Abdel-Gawad A. H., Atiya A. F., Darwish N. M. Solution of systems of Boolean equations via the integer domain // Information Sciences. 2010. Vol. 180, N 2. P. 288–300. https://doi.org/10.1016/j.ins.2009.09.010
  7. Armknecht F. Improving fast algebraic attacks // Fast Software Encryption: 11th International Workshop, FSE 2004, Delhi, India, February 5-7, 2004. Revised Papers 11. Springer Berlin Heidelberg, 2004. P. 65–82.
  8. Bard G. V. Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis. University of Maryland, College Park, 2007.
  9. Bardet M., Faugerebcd J. C., Salvye B., Spaenlehauer P. J. On the complexity of solving quadratic Boolean systems // Journal of Complexity. 2013. Vol. 29, N 1. P. 53–75. https://doi.org/10.1016/j.jco.2012.07.001
  10. Transformation method for solving system of Boolean algebraic equations / D. Barotov, A. Osipov, S. Korchagin, E. Pleshakova, D. Muzafarov, R. Barotov, D. Serdechnyy // Mathematics. 2021. Vol. 9 (24), 3299. https://doi.org/10.3390/math9243299
  11. Barotov D. N. Target Function without Local Minimum for Systems of Logical Equations with a Unique Solution // Mathematics. 2022. Vol. 10 (12), 2097. https://doi.org/10.3390/math10122097
  12. Barotov D. N., Barotov R. N. Polylinear Transformation Method for Solving Systems of Logical Equations // Mathematics. 2022. Vol. 10, 918. https://doi.org/10.3390/math10060918
  13. The Development of Suitable Inequalities and Their Application to Systems of Logical Equations / D. N. Barotov, R. N. Barotov, V. Soloviev, V. Feklin, D. Muzafarov, T. Ergashboev, K. Egamov // Mathematics. 2022. Vol. 10, 1851. https://doi.org/10.3390/math10111851
  14. Brown F. M. Boolean Reasoning: The logic of Boolean Equations. Boston : Kluwer Academic Publishers, 1990.
  15. Courtois N. T. Fast algebraic attacks on stream ciphers with linear feedback // Advances in Cryptology-CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003. Proceedings 23. Heidelberg : Springer Berlin, 2003. P. 176–194.
  16. Faugere J. C., Joux A. Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Grobner bases // Annual International Cryptology Conference. Heidelberg : Springer Berlin, 2003. P. 44–60.
  17. Faugere J. C. A new efficient algorithm for computing Grobner bases (F4) // Journal of pure and applied algebra. 1999. Vol. 139, N. 1-3. P. 61–88. https://doi.org/10.1016/S0022-4049(99)00005-5
  18. Faugere J. C. A new efficient algorithm for computing Grobner bases without reduction to zero (F5) // Proceedings of the 2002 international symposium on Symbolic and algebraic computation. 2002. P. 75–83.
  19. Gu J. Global optimization for satisfiability (SAT) problem // IEEE Transactions on Knowledge and Data Engineering. 1994. Vol. 6, N. 3. P. 361–381. https://doi.org/10.1109/69.334864
  20. Gu J. How to Solve Very Large-Scale Satisfiability (VLSS) Problems // Technical Report UCECETR-90-002. Calgary : University of Calgary, 1990.
  21. Gu J. On optimizing a search problem // Artificial Intelligence Methods and Applications. 1992. P. 63–105. https://doi.org/10.1142/9789814354707_0002
  22. Gu J., Gu Q., Du D. On optimizing the satisfiability (SAT) problem // Journal of Computer Science and Technology. 1999. Vol. 14, N 1. P. 1–17. https://doi.org/10.1007/BF02952482
  23. Hammer P. L., Rudeanu S. Boolean Methods in Operations Research and Related Areas. Berlin : Springer Verlag, 1968.
  24. Jensen J. L. W. V. Sur les fonctions convexes et les inegalites entre les valeurs moyennes // Acta mathematica. 1906. Vol. 30, N. 1. P. 175–193. https://doi.org/10.1007/BF02418571
  25.  Liu M., Lin D., Pei D. Fast algebraic attacks and decomposition of symmetric Boolean functions // IEEE Transactions on Information Theory. 2011. Vol. 57, N 7. P. 4817–4821. https://doi.org/10.1109/TIT.2011.2145690
  26. Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis / A. I. Pakhomchik, V. V. Voloshinov, V. M. Vinokur, G. B. Lesovik // Algorithms. 2022. Vol. 15, 33. https://doi.org/10.3390/a15020033

Полная версия (русская)