Сложность задач комбинаторной оптимизации в терминах решёток граней ассоциированных многогранников

Основной мотивацией работы является следующий вопрос, связанный со свойствами многогранников, ассоциированных с задачами комбинаторной оптимизации. Можно ли, зная комбинаторные свойства многогранника, оценить сложность соответствующей оптимизационной задачи? В разное время в качестве таких ключевых характеристик сложности рассматривались число гиперграней многогранника, диаметр и кликовое число его графа, число прямоугольного покрытия матрицы инциденций вершин-гиперграней и некоторые другие. В настоящей работе приводится несколько примеров семейств многогранников, для которых значения упомянутых выше характеристик существенно отличаются от реальной вычислительной сложности соответствующих оптимизационных задач. В частности, приводятся примеры двух задач дискретной оптимизации, многогранники которых комбинаторно эквивалентны и длины двоичной записи координат вершин этих многогранников одинаковы. При этом первая задача разрешима за полиномиальное время, а вторая задача имеет экспоненциальную сложность. Ил. 1, библиогр. 22.