Анализ сложности многогранников задач комбинаторной оптимизации

Многие современные эффективные алгоритмы решения задач комбинаторной оптимизации основаны на рассмотрении так называемых ассоциированных многогранников. Особое внимание в этом направлении уделяется изучению свойств выпуклых многогранников (а точнее — семейств многогранников), ассоциированных с NP-трудными задачами (задача коммивояжера, задача о рюкзаке, задача выполнимости булевых формул, задача о раскраске графа и т.п.). Накопленные к настоящему времени факты говорят о том, что упомянутые многогранники обладают рядом схожих свойств, существенно отличающихся от свойств многогранников, ассоциированных с известными полиномиально–разрешимыми задачами (задача о назначениях, задача о минимальном остовном дереве, задача о кратчайшем пути и др.). Наиболее интересными примерами таких свойств являются: экспоненциальное кликовое число графа многогранника и экспоненциальная сложность прямоугольного покрытия матрицы инциденций вершин–гиперграней многогранника.
По аналогии с классической полиномиальной сводимостью С. Кука, Р. Карпа и Л. А. Левина, автор доклада вводит понятие аффинной сводимости семейств многогранников, основанное на следующем естественном способе сравнения многогранников. Если многогранник $P$ аффинно эквивалентен либо самому многограннику $Q$, либо некоторой его грани (не обязательно гиперграни), будем говорить, что $P$ не сложнее $Q$. Оказалось, что при таком способе сравнения семейства многогранников известных труднорешаемых задач выстраиваются в иерархическом порядке. При этом наиболее «простыми» оказываются разрезные многогранники, а наиболее «сложными» — многогранники задачи коммивояжера. Слово «сложный» («простой») в данном случае следует интерпретировать как наличие (отсутствие) дополнительных особенностей, или же деталей. Кроме того, были построены примеры семейств булевых $p$–степенных многогранников, существенно более «простых», чем разрезные многогранники. Также было обнаружено, что при снятии ограничения невырожденности аффинного отображения в определении аффинной сводимости, вся описанная иерархия коллапсирует в один класс эквивалентности. Таким образом, обнаруженные взаимосвязи между семействами многогранников труднорешаемых задач выявляют глубинные причины сходства свойств, определяющих сложность.
С другой стороны, будут представлены несколько специальным образом сконструированных примеров задач комбинаторной оптимизации, для многогранников которых указанные выше свойства (кликовое число графа и сложность прямоугольного покрытия матрицы инциденций вершин–гиперграней) существенно отличаются от реальной вычислительной сложности задачи. Более того, будет доказана несостоятельность попыток оценки сложности задачи с помощью комбинаторных характеристик соответствующего многогранника.