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

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

Баротов Д. Н.
Дискретный анализ и исследование операций, 31, 1, 5-18 (2024)
Скачать статью

УДК 519.85+517.518.244 
DOI: 10.33048/daio.2024.31.779

Аннотация:

Строится выпуклое продолжение произвольной булевой функции на множество $[0, 1]^n$. Более того, доказывается, что для любой булевой функции $f(x_1, x_2, \dots, x_n)$, не имеющей соседних точек на множестве supp $f$, построенная функция $f_{C}(x_1, x_2, . . . , x_n)$ является единственным суммарно максимально выпуклым продолжением на $[0, 1]^n$. На базе этого, в частности, конструктивно утверждается, что задача решения произвольной системы булевых уравнений может быть сведена к задаче минимизации функции, любой локальный минимум которой в искомой области является глобальным минимумом, и тем самым для этой задачи проблема локальных минимумов полностью решается. 
Библиогр. 15.

Литература:
  1. Abdel-Gawad A. H., Atiya A. F., Darwish N. M. Solution of systems of Boolean equations via the integer domain // Inf. Sci. 2010. V. 180, No. 2. P. 288–300. DOI: 10.1016/j.ins.2009.09.010.
     
  2. Barotov D. N., Barotov R. N. Polylinear transformation method for solving systems of logical equations // Mathematics. 2022. V. 10, No. 6. Paper ID 918. 10 p. DOI: 10.3390/math10060918.
     
  3. Barotov D. N. Target function without local minimum for systems of logical equations with a unique solution // Mathematics. 2022. V. 10, No. 12. Paper ID 2097. 8 p. DOI: 10.3390/math10122097.
     
  4. Armario J. A. Boolean functions and permanents of Sylvester Hadamard matrices // Mathematics. 2021. V. 9, No. 2. Paper ID 177. 8 p. DOI: 10.3390/math9020177.
     
  5. Valiant L. G. The complexity of computing the permanent // Theor. Comput. Sci. 1979. V. 8, No. 2. P. 189–201. DOI: 10.1016/0304-3975(79)90044-6.
     
  6. Файзуллин Р. Т., Дулькейт В. И., Огородников Ю. Ю. Гибридный метод поиска приближенного решения задачи 3-выполнимость, ассоциированной с задачей факторизации // Тр. Ин-та математики и механики. 2013. Т. 19, № 2. C. 285–294.
     
  7. Gu J. Global optimization for satisfiability (SAT) problem // IEEE Trans. Knowl. Data Eng. 1994. V. 6, No. 3. P. 361–381. DOI: 10.1109/69.334864.
     
  8. Gu J., Gu Q., Du D. On optimizing the satisfiability (SAT) problem // J. Comput. Sci. Technol. 1999. V. 14, No. 1. P. 1–17. DOI: 10.1007/BF02952482.
     
  9. Pakhomchik A. I., Voloshinov V. V., Vinokur V. M., Lesovik G. B. Converting of Boolean expression to linear equations, inequalities and QUBO penalties for cryptanalysis // Algorithms. 2022. V. 15, No. 2. Paper ID 33. 22 p. DOI: 10.3390/a15020033.
     
  10. Barotov D. N., Barotov R. N., Soloviev V., Feklin V., Muzafarov D., Ergashboev T., Egamov Kh. The development of suitable inequalities and their application to systems of logical equations // Mathematics. 2022. V. 10, No. 11. Paper ID 1851. 9 p. DOI: 10.3390/math10111851.
     
  11. Баротов Д. Н., Баротов Р. Н. Полилинейные продолжения некоторых дискретных функций и алгоритм их нахождения // Вычисл. методы и программирование. 2023. Т. 24, вып. 1. С. 10–23. DOI: 10.26089/NumMet.v24r102.
     
  12. Barotov D. N., Osipov A., Korchagin S., Pleshakova E., Muzafarov D., Barotov R. N., Serdechnyi D. Transformation method for solving system of Boolean algebraic equations // Mathematics. 2021. V. 9, No. 24. Paper ID 3299. 12 p. DOI: 10.3390/math9243299.
     
  13. Owen G. Multilinear extensions of games // Manage. Sci. 1972. V. 18, No. 5-2. P. 64–79. DOI: 10.1287/mnsc.18.5.64.
     
  14. Wittmann D. M., Krumsiek J., Saez-Rodriguez J., Lauffenburger D. A., Klamt S., Theis F. J. Transforming Boolean models to continuous models: Methodology and application to T-cell receptor signaling // BMC Syst. Biol. 2009. V. 3, No. 1. Paper ID 98. 21 p. DOI: 10.1186/1752-0509-3-98.
     
  15. Jensen J. L. W. V. Sur les fonctions convexes et les inégalités entre les valeurs moyennes // Acta Math. 1906. V. 30. P. 175–193. [French]. DOI: 10.1007/BF02418571.

Исследование выполнено за счёт бюджета Финансового университета при Правительстве Российской Федерации. Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Баротов Достонжон Нумонжонович
  1. Финансовый университет при Правительстве Российской Федерации,  
    4-й Вешняковский пр-д, 4, 109456 Москва, Россия

E-mail: dnbarotov@fa.ru

Статья поступила 17 июля 2023 г. 
После доработки — 4 августа 2023 г. 
Принята к публикации 22 сентября 2023 г.

Abstract:

A convex continuation of an arbitrary Boolean function to the set $[0, 1]^n$ is constructed. Moreover, it is proved that for any Boolean function $f(x_1, x_2, \dots , x_n)$ that has no neighboring points on the set supp $f$, the constructed function $f_{C}(x_1, x_2, \dots , x_n)$ is the only totally maximally convex continuation to $[0, 1]^n$. Based on this, in particular, it is constructively stated that the problem of solving an arbitrary system of Boolean equations can be reduced to the problem of minimizing a function any local minimum of which in the desired region is a global minimum, and thus for this problem the problem of local minima is completely resolved. 
Bibliogr. 15.

References:
  1. A. H. Abdel-Gawad, A. F. Atiya, and N. M. Darwish, Solution of systems of Boolean equations via the integer domain, Inf. Sci. 180 (2), 288–300 (2010), DOI: 10.1016/j.ins.2009.09.010.
     
  2. D. N. Barotov and R. N. Barotov, Polylinear transformation method for solving systems of logical equations, Mathematics 10 (6), ID 918 (2022), DOI: 10.3390/math10060918.
     
  3. D. N. Barotov, Target function without local minimum for systems of logical equations with a unique solution, Mathematics 10 (12), ID 2097 (2022), DOI: 10.3390/math10122097.
     
  4. J. A. Armario, Boolean functions and permanents of Sylvester Hadamard matrices, Mathematics 9 (2), ID 177 (2021), DOI: 10.3390/math9020177.
     
  5. L. G. Valiant, The complexity of computing the permanent, Theor. Comput. Sci. 8 (2), 189–201 (1979), DOI: 10.1016/0304-3975(79)90044-6.
     
  6. R. T. Faizullin, V. I. Dul’keit, and Yu. Yu. Ogorodnikov, Hybrid method for the approximate solution of the 3-satisfiability problem associated with the factorization problem, Tr. Inst. Mat. Mekh. 19 (2), 285–294 (2013) [Russian].
     
  7. J. Gu, Global optimization for satisfiability (SAT) problem, IEEE Trans. Knowl. Data Eng. 6 (3), 361–381 (1994), DOI: 10.1109/69.334864.
     
  8. J. Gu, Q. Gu, and D. Du, On optimizing the satisfiability (SAT) problem, J. Comput. Sci. Technol. 14 (1), 1–17 (1999), DOI: 10.1007/BF02952482.
     
  9. A. I. Pakhomchik, V. V. Voloshinov, V. M. Vinokur, and G. B. Lesovik, Converting of Boolean expression to linear equations, inequalities and QUBO penalties for cryptanalysis, Algorithms 15 (2), ID 33 (2022), DOI: 10.3390/a15020033.
     
  10. D. N. Barotov, R. N. Barotov, V. Soloviev, V. Feklin, D. Muzafarov, T. Ergashboev, and Kh. Egamov, The development of suitable inequalities and their application to systems of logical equations, Mathematics 10 (11), ID 1851 (2022), DOI: 10.3390/math10111851.
     
  11. D. N. Barotov and R. N. Barotov, Polylinear continuations of some discrete functions and an algorithm for finding them, Vychisl. Metody Program. 24 (1), 10–23 (2023) [Russian], DOI: 10.26089/NumMet.v24r102.
     
  12. D. N. Barotov, A. Osipov, S. Korchagin, E. Pleshakova, D. Muzafarov, R. N. Barotov, and D. Serdechnyi, Transformation method for solving system of Boolean algebraic equations, Mathematics 9 (24), ID 3299 (2021), DOI: 10.3390/math9243299.
     
  13. G. Owen, Multilinear extensions of games, Manage. Sci. 18 (5-2), 64–79 (1972), DOI: 10.1287/mnsc.18.5.64.
     
  14. D. M. Wittmann, J. Krumsiek, J. Saez-Rodriguez, D. A. Lauffenburger, S. Klamt, and F. J. Theis, Transforming Boolean models to continuous models: Methodology and application to T-cell receptor signaling, BMC Syst. Biol. 3 (1), ID 98 (2009), DOI: 10.1186/1752-0509-3-98.
     
  15. J. L. W. V. Jensen, Sur les fonctions convexes et les inégalités entre les valeurs moyennes, Acta Math. 30, 175–193 (1906) [French], DOI: 10.1007/BF02418571.