EN|RU

Том 18, номер 3, 2011 г., Стр. 76-83

УДК 519.85
Максименко А. Н.
Многогранники задачи о выполнимости являются гранями многогранника задачи коммивояжёра

Аннотация:
Пусть на множестве булевых переменных $U=\{u_1,u_2,\dots,u_d\}$ задана булева формула $C$ в конъюнктивной нормальной форме. Обозначим через $Y\subset\mathbb R^d$ множество характеристических векторов всех выполняющих $C$ наборов значений переменных. Многогранником задачи о выполнимости $S(U,C)$ назовём выпуклую оболочку множества $Y$. Многогранник коммивояжёра для орграфа на $n$ вершинах обозначим через $T_n$. Показано, что $S(U,C)$ аффинно эквивалентен некоторой грани многогранника $T_n$, где $n=|U|+2\operatorname{len}(C)$, $\operatorname{len}(C)$ – длина формулы $C$ в литералах.
Ил. 1, библиогр. 9.

Ключевые слова: многогранник коммивояжёра, многогранник задачи о выполнимости, грань.

Максименко Александр Николаевич 1
1. Ярославский гос. университет им. П. Г. Демидова,
ул. Союзная, 144, 150008 Ярославль, Россия
е-mail: maksimenko_a_n@mail.ru

Статья поступила 19 июля 2010 г.
Исправленный вариант — 15 марта 2011 г.

 © Институт математики им. С. Л. Соболева, 2015