Czy programowanie liniowe dopuszcza algorytm silnie wielomianowy?

12

Problem programowania liniowego: znajdź algorytm silnie wielomianowy, który dla danej macierzy A ∈ Rm × n i b ∈ Rm decyduje, czy istnieje x ∈ Rn z Ax ≥ b.

Wiem, że Steve Smale wymienia niektóre nierozwiązane problemy matematyki. Ale czy taki liniowy problem programowania jest do tej pory nierozwiązywalny?

algorithms polynomial-time linear-programming Krebto
źródło
Problemy z programowaniem liniowym wydają się rozwiązywane w czasie wielomianowym za pomocą algorytmu Simplex, to tylko dowód, którego brakuje. Plus problem, że mogą istnieć kontrprzykłady, ale wydaje się, że bardzo trudno je znaleźć.
gnasher729,
2
@ gnasher729 Znane są kontrprzykłady, np . kostka Klee-Minty . Z drugiej strony istnieją algorytmy punktów wewnętrznych, o których wiadomo, że działają w (słabo) czasie wielomianowym.
Tavian Barnes,
Artykuł dotyczy: cc.gatech.edu/~vempala/papers/affine.pdf
Erel Segal-Halevi

Odpowiedzi:

12

Ten problem jest nadal otwarty. Zobacz na przykład Wikipedię , która choć ogólnie nie jest niezawodnym źródłem, prawdopodobnie zostanie zaktualizowana, jeśli kiedykolwiek zostanie znaleziony algorytm silnie wielomianowy.

Yuval Filmus
źródło