О порядке гладкости максимального выпуклого продолжения булевой функции
https://doi.org/10.22405/2226-8383-2025-26-3-58-70
Аннотация
Данная статья посвящена установлению порядка гладкости 𝑓𝑁𝑅(𝑥1, 𝑥2, ..., 𝑥𝑛) — наибольшего выпуклого продолжения на [0, 1]𝑛 любой булевой функции 𝑓𝐵(𝑥1, 𝑥2, ..., 𝑥𝑛). В результате исследования для каждой булевой функции 𝑓𝐵(𝑥1, 𝑥2, ..., 𝑥𝑛) установлен порядок
дифференцируемости 𝑓𝑁𝑅(𝑥1, 𝑥2, ..., 𝑥𝑛) — соответствующего ей наибольшего выпуклого продолжения на [0, 1]𝑛, а именно, во-первых, с обеих сторон оценено наибольшее выпуклое продолжение 𝑓𝑁𝑅(𝑥1, 𝑥2, ..., 𝑥𝑛) так, что из чего следует непрерывность 𝑓𝑁𝑅(𝑥1, 𝑥2, ..., 𝑥𝑛) на [0, 1]𝑛 для любого натурального 𝑛, а во-вторых, доказано, что если число существенных переменных булевой функции 𝑓𝐵(𝑥1, 𝑥2, ..., 𝑥𝑛) меньше двух, то на [0, 1]𝑛 наибольшее выпуклое продолжение 𝑓𝑁𝑅(𝑥1, 𝑥2, ..., 𝑥𝑛) бесконечно дифференцируемо, а если не мень-
ше двух, то на [0, 1]𝑛 наибольшее выпуклое продолжение 𝑓𝑁𝑅(𝑥1, 𝑥2, ..., 𝑥𝑛) не является дифференцируемым, т. е. является лишь непрерывным.
Об авторах
Достонжон Нумонжонович Баротов
Финансовый университет при Правительстве Российской Федерации
Россия
Россия
Рузибой Нумонжонович Баротов
Худжандский государственный университет имени академика Б. Гафурова
Таджикистан
Таджикистан
Список литературы
1. Brown F. M. Boolean Reasoning: The logic of Boolean Equations. Kluwer Academic Publishers, Boston, 1990.
2. Баротов, Д. Н., Баротов, Р. Н. Об одном приведении системы булевых уравнений к эквивалентной системе полиномиальных уравнений // Математические структуры и моделирование. 2024. № 1(69). С. 5–17. doi: 10.24147/2222-8772.2024.1.5-17.
3. Hammer, P. L., Rudeanu, S. Boolean Methods in Operations Research and Related Areas. Springer Verlag, Berlin, 1968.
4. Баротов, Д. Н., Баротов, Р. Н. Конструирование гладких выпуклых продолжений булевых функций // Вестник российских университетов. Математика. 2024. Т. 29. № 145. С. 20—28. doi:10.20310/2686-9667-2024-29-145-20-28.
5. 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.
6. Faugere, J. C., Joux, A. Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Grobner bases // Annual International Cryptology Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. P. 44–60.
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. Bardet, M., Faugere, J. C., Salvye, B., Spaenlehauer, P. J. On the complexity of solving quadratic Boolean systems // Journal of Complexity. 2013. Vol. 29. no. 1. P. 53–75. doi: 10.1016/j.jco.2012.07.001.
9. 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. Springer Berlin Heidelberg, 2003. P. 176–194.
10. Liu, M., Lin, D., Pei, D. Fast algebraic attacks and decomposition of symmetric Boolean functions // IEEE Transactions on Information Theory. 2011. Vol. 57. no. 7. P. 4817–4821. doi: 10.1109/TIT.2011.2145690.
11. Gu, J. How to Solve Very Large-Scale Satisfiability (VLSS) Problems // Technical Report UCECETR-90-002, University of Calgary: Calgary, 1990.
12. Gu, J. On optimizing a search problem // Artificial Intelligence Methods and Applications. 1992. P. 63–105. doi: 10.1142/9789814354707_0002.
13. Баротов, Д. Н., Музафаров, Д. З., Баротов, Р. Н. Об одном методе решения систем булевых алгебраических уравнений // Современная математика и концепции инновационного математического образования. 2021. Т. 8, № 1. С. 17—23.
14. Gu, J. Global optimization for satisfiability (SAT) problem // IEEE Transactions on Knowledge and Data Engineering. 1994. Vol. 6. no. 3. P. 361–381. doi: 10.1109/69.334864.
15. Gu, J., Gu, Q., Du, D. On optimizing the satisfiability (SAT) problem // Journal of Computer Science and Technology. 1999. Vol. 14. no. 1. P. 1–17. doi: 10.1007/BF02952482.
16. Transformation method for solving system of Boolean algebraic equations / Barotov, D., Osipov, A., Korchagin, S., Pleshakova, E., Muzafarov, D., Barotov, R., Serdechnyy, D. // Mathematics. 2021. Vol. 9, 3299. doi: 10.3390/math9243299.
17. Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis / Pakhomchik, A. I., Voloshinov, V. V., Vinokur, V. M., Lesovik, G. B. // Algorithms. 2022. Vol. 15, 33. doi: 10.3390/a15020033.
18. Algebraic attacks on block ciphers using quantum annealing / Burek, E., Wronski, M., Mank, K., Misztal, M. // IEEE Transactions on Emerging Topics in Computing. 2022. Vol. 10. no. 2. P. 678—689. doi: 10.1109/TETC.2022.3143152.
19. 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, no. 2, P. 288–300. doi: 10.1016/j.ins.2009.09.010.
20. The Development of Suitable Inequalities and Their Application to Systems of Logical Equations / Barotov, D. N., Barotov, R. N., Soloviev, V., Feklin, V., Muzafarov, D., Ergashboev, T., Egamov, K. // Mathematics. 2022. Vol. 10, 1851. doi: 10.3390/math10111851.
21. Faugere, J. C. A new efficient algorithm for computing Grobner bases (F4) // Journal of pure and applied algebra. 1999. Vol. 139. no. 1-3. P. 61–88. doi: 10.1016/S0022-4049(99)00005-5.
22. 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.
23. Файзуллин, Р.Т., Дулькейт, В. И., Огородников, Ю.Ю. Гибридный метод поиска приближенного решения задачи 3-выполнимость, ассоциированной с задачей факторизации // Труды Института математики и механики УрО РАН. 2013. Т. 19, № . 2. С. 285–294.
24. Баротов, Д. Н., Баротов, Р. Н. Полилинейные продолжения некоторых дискретных функций и алгоритм их нахождения // Вычислительные методы и программирование. 2023. Т. 24. С. 10–23. doi: 10.26089/NumMet.v24r102.
25. Barotov, D. N. Target Function without Local Minimum for Systems of Logical Equations with a Unique Solution // Mathematics. 2022. Vol. 10, 2097. doi: 10.3390/math10122097.
26. Barotov, D. N., Barotov, R. N. Polylinear Transformation Method for Solving Systems of Logical Equations // Mathematics. 2022. Vol. 10, 918. doi: 10.3390/math10060918.
27. Баротов, Д. Н. Выпуклое продолжение булевой функции и его приложения // Дискретный анализ и исследование операций. 2024. Т. 31, № 1. С. 5–18. doi: 10.33048/daio.2024.31.779.
28. Баротов, Д. Н. О существовании и свойствах выпуклых продолжений булевых функций // Матем. заметки. 2024. Т. 115, № 4. С. 533—551. doi: 10.4213/mzm14105.
29. Баротов, Д. Н., Судаков, В. А. О неравенствах между выпуклыми, вогнутыми и полилинейными продолжениями булевых функций // Препринты ИПМ им. М.В. Келдыша. 2024. № 30. С. 1–13. doi: 10.20948/prepr-2024-30.
30. Баротов, Д. Н. Вогнутые продолжения булевых функций и некоторые их свойства и приложения // Известия Иркутского государственного университета. Серия ≪Математика≫. 2024. Т. 49. С. 105–123. doi: 10.26516/1997-7670.2024.49.105.
31. Баротов, Д. Н. Выпуклые продолжения некоторых дискретных функций // Дискретный анализ и исследование операций. 2024. Т. 31, № 3. С. 5–23. doi: 10.33048/daio.2024.31.789.
32. Jensen, J. L. W. V. Sur les fonctions convexes et les inegalites entre les valeurs moyennes // Acta mathematica. 1906. Vol. 30. no. 1. P. 175–193. doi: 10.1007/BF02418571.
Рецензия
Для цитирования:
Баротов Д.Н., Баротов Р.Н. О порядке гладкости максимального выпуклого продолжения булевой функции. Чебышевский сборник. 2025;26(3):58-70. https://doi.org/10.22405/2226-8383-2025-26-3-58-70
For citation:
Barotov D.N., Barotov R.N. On the order of smoothness of the maximal convex continuation of a Boolean function. Chebyshevskii Sbornik. 2025;26(3):58-70. (In Russ.) https://doi.org/10.22405/2226-8383-2025-26-3-58-70
Просмотров:
5
Послать статью по эл. почте 