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?
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,
@ 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