Допускает ли линейное программирование сильно полиномиальный алгоритм?

12

Задача линейного программирования: найти сильно полиномиальный алгоритм времени, который для заданной матрицы A ∈ Rm × n и b ∈ Rm решает, существует ли x ∈ Rn с Ax ≥ b.

Я знаю, что в списке Стива Смейла перечислены некоторые нерешенные проблемы математики. Но такая проблема линейного программирования до сих пор не решаема?

algorithms polynomial-time linear-programming Krebto
источник
Проблемы линейного программирования, кажется, решаются за полиномиальное время с помощью алгоритма Simplex, это просто доказательство, которое отсутствует. Плюс проблема в том, что могут быть встречные примеры, но их, похоже, очень сложно найти.
gnasher729
2
@ gnasher729 Существуют известные контрпримеры, например, куб Кли-Минти . С другой стороны, известны алгоритмы внутренних точек, которые работают за (слабо) полиномиальное время.
Тавиан Барнс
Этот документ связан с: cc.gatech.edu/~vempala/papers/affine.pdf
Сегал-Халеви,

Ответы:

12

Эта проблема все еще открыта. См., Например, Википедию , которая, хотя и не является надежным источником в целом, вероятно, будет обновлена, если когда-либо будет найден сильно полиномиальный алгоритм времени.

Юваль Фильмус
источник