Geodesic
Construction of smooth convex extensions of Boolean functions
Vestnik rossijskih universitetov. Matematika, Tome 29 (2024) no. 145, pp. 20-28 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Systems of Boolean equations are widely used in mathematics, computer science, and applied sciences. In this regard, on the one hand, new research methods and algorithms are being developed for such systems, and on the other hand, existing methods and algorithms for solving such systems are being improved. One of these methods is that, firstly, the system of Boolean equations given over the ring of Boolean polynomials is transformed into a system of equations over the field of real numbers, and secondly, the transformed system is reduced either to the problem of numerical minimization of the corresponding objective function, to a MILP or QUBO problem, to a system of polynomial equations solved on the set of integers, or to an equivalent system of polynomial equations solved by symbolic methods. There are many ways to transform a system of Boolean equations into a continuous minimization problem, since the fundamental difference between such methods and “brute force” local search algorithms is that at each iteration of the algorithm, the shift along the antigradient is performed on all variables simultaneously. But one of the main problems that arise when applying these methods is that the objective function to be minimized in the desired area can have many local minima, which greatly complicates their practical use. In this paper, a non-negative convex and continuously differentiable extension of any Boolean function is constructed, which is applied to solving an arbitrary system of Boolean equations. It is argued that the problem of solving an arbitrary system of Boolean equations can be constructively reduced to the problem of minimizing a function, any local minimum of which in the desired domain is a global minimum.
Keywords: global optimization, convex function, Boolean function, extension of a Boolean function, local minimum 
@article{VTAMU_2024_29_145_a1,
     author = {D. N. Barotov and R. N. Barotov},
     title = {Construction of smooth convex extensions of {Boolean} functions},
     journal = {Vestnik rossijskih universitetov. Matematika},
     pages = {20--28},
     year = {2024},
     volume = {29},
     number = {145},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTAMU_2024_29_145_a1/}
}
TY  - JOUR
AU  - D. N. Barotov
AU  - R. N. Barotov
TI  - Construction of smooth convex extensions of Boolean functions
JO  - Vestnik rossijskih universitetov. Matematika
PY  - 2024
SP  - 20
EP  - 28
VL  - 29
IS  - 145
UR  - http://geodesic.mathdoc.fr/item/VTAMU_2024_29_145_a1/
LA  - ru
ID  - VTAMU_2024_29_145_a1
ER  - 
%0 Journal Article
%A D. N. Barotov
%A R. N. Barotov
%T Construction of smooth convex extensions of Boolean functions
%J Vestnik rossijskih universitetov. Matematika
%D 2024
%P 20-28
%V 29
%N 145
%U http://geodesic.mathdoc.fr/item/VTAMU_2024_29_145_a1/
%G ru
%F VTAMU_2024_29_145_a1
D. N. Barotov; R. N. Barotov. Construction of smooth convex extensions of Boolean functions. Vestnik rossijskih universitetov. Matematika, Tome 29 (2024) no. 145, pp. 20-28. http://geodesic.mathdoc.fr/item/VTAMU_2024_29_145_a1/

[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 | DOI | MR | Zbl

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

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

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

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

[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, no. 2 (2013), 285–294 (In Russian) | MR

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

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

[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 | DOI

[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 | DOI

[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 | DOI

[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 | DOI

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

[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) | DOI

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