Эта публикация цитируется в
4 статьях
Выпуклое продолжение булевой функции и его приложения
Д. Н. Баротов Финансовый университет при Правительстве Российской Федерации, 4-й Вешняковский пр-д, 4, 109456 Москва, Россия
Аннотация:
Строится выпуклое продолжение произвольной булевой функции на множество
$[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
DOI:
10.33048/daio.2024.31.779