|
This article is cited in 4 scientific papers (total in 4 papers)
Convex continuation of a Boolean function and its applications
D. N. Barotov Financial University under the Government of the Russian Federation, 4 Chetvyortyi Veshnyakovskii Passage, 109456 Moscow, Russia
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 $\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.
Received: 17.07.2023 Revised: 04.08.2023 Accepted: 22.09.2023
Citation:
D. N. Barotov, “Convex continuation of a Boolean function and its applications”, Diskretn. Anal. Issled. Oper., 31:1 (2024), 5–18; J. Appl. Industr. Math., 18:1 (2024), 1–9
Linking options:
https://www.mathnet.ru/eng/da1336 https://www.mathnet.ru/eng/da/v31/i1/p5
|
Statistics & downloads: |
Abstract page: | 101 | Full-text PDF : | 3 | References: | 24 | First page: | 11 |
|