RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2024 Volume 31, Issue 1, Pages 5–18 (Mi da1336)

This article is cited in 2 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.

UDC: 519.85+517.518.244

Received: 17.07.2023
Revised: 04.08.2023
Accepted: 22.09.2023

DOI: 10.33048/daio.2024.31.779


 English version:
Journal of Applied and Industrial Mathematics, 2024, 18:1, 1–9


© Steklov Math. Inst. of RAS, 2024