Многогранники задачи о выполнимости являются гранями многогранника задачи коммивояжёра

Пусть на множестве булевых переменных $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.