RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2024, том 31, выпуск 1, страницы 5–18 (Mi da1336)

Эта публикация цитируется в 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


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2024, 18:1, 1–9


© МИАН, 2024