Вычислительная сложность линейного программирования

Версия задачи линейного программирования с принятием решения принадлежит NP. Интуитивно это вполне понятно — нужно лишь представить вектор x,
обладающий нужными свойствами.

Единственная проблема в том, что даже если все входные числа являются целыми, координаты такого вектора x могут быть нецелыми, и для их представления может потребоваться очень большая точность: откуда известно, что мы сможем читать и обрабатывать эти данные за полиномиальное время?

Но на самом деле можно показать, что если решение существует, то существует и рациональное решение, для записи которого достаточно полиномиального количества битов, так что это не проблема.

В течение долгого времени линейное программирование, пожалуй, было самым известным примером задачи, принадлежащей NP и co-NP, для которой не известно

Читатели, знакомые со свойством двойственности, могут также заметить, что метод назначения цены из предыдущего раздела также работает на основе двойственности линейного программирования: цены точно соответствуют переменным в двойственной задаче линейного программирования (и это объясняет, почему алгоритмы назначения цены часто называются прямодвойственными алгоритмами).

Затем в 1981 году Леонид Хачиян, который в то время был молодым ученым из СССР, предложил алгоритм с полиномиальным временем для этой задачи.

Американская массовая пресса забеспокоилась, не сыграет ли это открытие ту же роль, что и запуск спутника в период холодной войны, но этого не произошло, и вскоре ученые разобрались в том, что же сделал Хачиян.

Его исходный алгоритм работал с полиномиальным временем, но был довольно медленным и непригодным для практического применения; но с тех пор после выхода работы Нарендры Кармаркара в 1984 году были разработаны практичные алгоритмы с полиномиальным временем — так называемые методы внутренней точки. Пример линейного программирования также интересен и по другой причине.

Самым распространенным алгоритмом для решения этой задачи является симплексный метод. Он очень хорошо работает на практике и в реальных задачах может успешно конкурировать с внутренними методами, работающими с полиномиальным временем.

Тем не менее известно, что в худшем случае он выполняется за полиномиальное время; просто экспоненциальное поведение очень редко встречается на практике.

По этой причине линейное программирование стало очень полезным и важным примером для анализа ограничений полиномиального времени как формального определения эффективности.

Впрочем, для наших целей важно то, что задачи линейного программирования могут решаться за полиномиальное время, и на практике существуют очень эффективные алгоритмы.

На курсах линейного программирования вы сможете получить гораздо больше информации по этой теме, а нас сейчас интересует следующий вопрос: как линейное программирование помогает при решении таких комбинаторных задач, как задача о вершинном покрытии?