Одним из основных принципов разработки алгоритма является нахождение сильно полиномиального алгоритма для линейного программирования, т. Е. Алгоритма, время выполнения которого ограничено полиномом по числу переменных и ограничений и не зависит от размера представления параметров (при условии арифметика удельной стоимости). Будет ли решение этого вопроса иметь значение за пределами лучших алгоритмов для линейного программирования? Например, будет ли существование / отсутствие такого алгоритма иметь какие-либо последствия для геометрии или теории сложности?
Изменить: Может быть, я должен уточнить, что я имею в виду под последствиями. Я ищу математические последствия или условные результаты, последствия, которые, как известно, сейчас верны . Например: «полиномиальный алгоритм для LP в модели BSS разделил бы / свернул классы алгебраической сложности FOO и BAR», или «если нет строго полиномиального алгоритма, он разрешает такую-то гипотезу о многогранниках», или «a сильно полиномиальный алгоритм для задачи X, который может быть сформулирован как LP, будет иметь интересные последствия, бла ". Гипотеза Хирша была бы хорошим примером, за исключением того, что она применима, только если симплекс полиномиален.
Ответы:
Это показало бы, что игры с паритетом и средним выигрышем находятся в P. См. Sven Schewe. От игр четности и выигрыша до линейного программирования. MFCS 2009.
источник
источник
Вот одно следствие для геометрии: сильно полиномиальная оценка для любого варианта (рандомизированного или детерминированного) симплексного алгоритма подразумевает полиномиальную оценку для диаметра любого многогранника графа. Это подразумевает, что «полиномиальная версия» гипотезы Гирша верна.
источник