Geodesic
Convex continuation of a Boolean function and its applications
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 1, pp. 5-18 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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 $\mathrm{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.
Keywords: convex continuation of a function, system of Boolean equations, SAT, global optimization, Boolean function, local minimum. 
@article{DA_2024_31_1_a0,
     author = {D. N. Barotov},
     title = {Convex continuation of {a~Boolean} function and~its~applications},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--18},
     year = {2024},
     volume = {31},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_1_a0/}
}
TY  - JOUR
AU  - D. N. Barotov
TI  - Convex continuation of a Boolean function and its applications
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 5
EP  - 18
VL  - 31
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_1_a0/
LA  - ru
ID  - DA_2024_31_1_a0
ER  - 
%0 Journal Article
%A D. N. Barotov
%T Convex continuation of a Boolean function and its applications
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 5-18
%V 31
%N 1
%U http://geodesic.mathdoc.fr/item/DA_2024_31_1_a0/
%G ru
%F DA_2024_31_1_a0
D. N. Barotov. Convex continuation of a Boolean function and its applications. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 1, pp. 5-18. http://geodesic.mathdoc.fr/item/DA_2024_31_1_a0/

[1] Abdel-Gawad A. H., Atiya A. F., Darwish N. M., “Solution of systems of Boolean equations via the integer domain”, Inf. Sci., 180:2 (2010), 288–300 | DOI | MR | Zbl

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

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

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

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

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

[7] Gu J., “Global optimization for satisfiability (SAT) problem”, IEEE Trans. Knowl. Data Eng., 6:3 (1994), 361–381 | DOI

[8] Gu J., Gu Q., Du D., “On optimizing the satisfiability (SAT) problem”, J. Comput. Sci. Technol., 14:1 (1999), 1–17 | DOI | MR

[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, 15:2 (2022), 33, 22 pp. | DOI

[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, 10:11 (2022), 1851, 9 pp. | DOI

[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 (2023), 10–23 (Russian) | DOI

[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, 9:24 (2021), 3299, 12 pp. | DOI

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

[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., 3:1 (2009), 98, 21 pp. | DOI

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