Аннотация:
Строится выпуклое продолжение произвольной булевой функции на множество $[0,1]^n$. Более того, доказывается, что для любой булевой функции $f(x_1,x_2,\dots,x_n)$, не имеющей соседних точек на множестве $\mathrm{supp}\,f$, построенная функция $f_C(x_1,x_2,\dots,x_n)$ является единственным суммарно максимально выпуклым продолжением на $[0,1]^n$. На базе этого, в частности, конструктивно утверждается, что задача решения произвольной системы булевых уравнений может быть сведена к задаче минимизации функции, любой локальный минимум которой в искомой области является глобальным минимумом, и тем самым для этой задачи проблема локальных минимумов полностью решается. Библиогр. 15.
Ключевые слова:выпуклое продолжение функции, система булевых уравнений, SAT, безусловная оптимизация, булева функция, локальный минимум.
УДК:519.85+517.518.244
Статья поступила: 17.07.2023 Переработанный вариант: 04.08.2023 Принята к публикации: 22.09.2023