A special role of Boolean quadratic polytopes among other combinatorial polytopes

Рассматриваются несколько семейств комбинаторных многогранников, ассоциированных со следующими NP-полными задачами: максимальный разрез, булево квадратичное программирование, квадратичная задача линейного упорядочения, квадратичные назначения, разбиение и упаковка множества, независимое множество, $3$-назначения. Для сравнения двух семейств многогранников используется следующий способ. Будем говорить, что семейство $P$ аффинно сводится к семейству $Q$, если для каждого многогранника $p\in P$ найдется $q\in Q$ такой, что $p$ аффинно эквивалентен $q$ или некоторой грани $q$, где $\dim q = O((\dim p)^k)$ для некоторой константы $k$. При таком способе сравнения упомянутые выше семейства разбиваются на два класса эквивалентности. Показано также, что эти два класса проще (в указанном смысле), чем семейства многогранников следующих задач: покрытие множества, коммивояжер, $0/1$ рюкзак, $3$-выполнимость, кубический подграф, частичное упорядочение. В частности, булевы квадратичные многогранники оказываются гранями многогранников каждого из упомянутых семейств.
Статья публикуется в авторской редакции.