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

Системы булевых уравнений широко используются в математике, компьютерных и прикладных науках. В связи с этим, с одной стороны, для таких систем разрабатываются новые методы и алгоритмы исследования, а с другой — совершенствуются существующие методы и алгоритмы решения таких систем. Один из методов заключается в том, что, во-первых, система булевых уравнений, заданная над кольцом булевых полиномов, трансформируется в систему уравнений над полем действительных чисел, а во-вторых, трансформированная система сводится либо к задаче численной минимизации соответствующей целевой функции, либо к задаче MILP или QUBO, либо к системе полиномиальных уравнений, решаемой на множестве целых чисел, либо к эквивалентной системе полиномиальных уравнений, решаемой символьными методами. Имеется много способов, позволяющих трансформировать систему булевых уравнений в задачу непрерывной минимизации, поскольку принципиальное отличие таких методов от «переборных» алгоритмов локального поиска — на каждой итерации алгоритма сдвиг по антиградиенту производится по всем переменным одновременно. Но одна из основных проблем, возникающая при применении этих способов, состоит в том, что минимизируемая целевая функция в искомой области может иметь множество локальных минимумов, что значительно усложняет их практическое использование. В работе строится неотрицательное выпуклое и непрерывно дифференцируемое продолжение произвольной булевой функции, которое применяется к решению произвольной системы булевых уравнений. Утверждается, что задача решения произвольной системы булевых уравнений может быть конструктивно сведена к задаче минимизации функции, любой локальный минимум которой в искомой области является глобальным минимумом.

1. A.H. Abdel-Gawad, A.F. Atiya, N.M. Darwish, “Solution of systems of Boolean equations via the integer domain”, Information Sciences, 180:2 (2010), 288–300.

2. D.N. Barotov, R.N. Barotov, “Polylinear transformation method for solving systems of logical equations”, Mathematics, 10:6 (2022), 918.

3. D.N. Barotov, “Target function without local minimum for systems of logical equations with a unique solution”, Mathematics, 10:12 (2022), 2097.

4. J.A. Armario, “Boolean functions and permanents of Sylvester Hadamard matrices”, Mathematics, 9:2 (2021), 177.

5. L.G. Valiant, “The complexity of computing the permanent”, Theoretical Computer Science, 8:2 (1979), 189–201.

6. R.T. Faizullin, V.I. Dul’keit, Yu.Yu. Ogorodnikov, “Hybrid method for the approximate solution of the 3-satisfiability problem associated with the factorization problem”, Trudy Inst. Mat. i Mekh. UrO RAN, 19:2 (2013), 285–294 (In Russian).

7. J.Gu, “Global optimization for satisfiability (SAT) problem”, IEEE Transactions on Knowledge and DataEngineering, 6:3 (1994), 361–381.

8. J. Gu, Q. Gu, D. Du, “On optimizing the satisfiability (SAT) problem”, Journal of Computer Science and Technology, 14:1 (1999), 1–17.

9. A.I. Pakhomchik, V.V. Voloshinov, V.M. Vinokur, G.B. Lesovik, “Converting of Boolean expression to linear equations, inequalities and QUBO penalties for cryptanalysis”, Algorithms, 15:2 (2022), 33.

10. D.N. Barotov, R.N. Barotov, V. Soloviev, V. Feklin, D. Muzafarov, T. Ergashboev, Kh. Egamov, “The development of suitable inequalities and their application to systems of logical equations”, Mathematics, 10:11 (2022), 1851.

11. D.N. Barotov, R.N. Barotov, “Polylinear continuations of some discrete functions and an algorithm for finding them”, Numerical Methods and Programming (Vychislitel'nye Metody i Programmirovanie), 24:1 (2023), 10–23.

12. D.N. Barotov, A. Osipov, S. Korchagin, E. Pleshakova, D. Muzafarov, R. Barotov, D. Serdechnyy, “Transformation method for solving system of Boolean algebraic equations”, Mathematics, 9:24 (2021), 3299.

13. G. Owen, “Multilinear extensions of games”, Management Science, 18:(5-part-2) (1972), 64–79.

14. D.M. Wittmann, J. Krumsiek, J. Saez-Rodriguez, D.A. Lauffenburger, S. Klamt, F.J. Theis, “Transforming Boolean models to continuous models: methodology and application to T-cell receptor signaling”, BMC Systems Biology, 3 (2009), 98(2009).

15. J.L.W.V. Jensen, “Sur les fonctions convexes et les inegalites entre les valeurs moyennes”, Acta Mathematica, 30 (1906), 175–193.