Lässt die lineare Programmierung einen stark polynomiellen Zeitalgorithmus zu?

12

Das lineare Programmierproblem: Finden Sie einen stark polynomiellen Zeitalgorithmus, der für die gegebene Matrix A ∈ Rm × n und b ∈ Rm entscheidet, ob x ∈ Rn mit Ax ≥ b existiert.

Ich weiß, dass Steve Smale einige der ungelösten Probleme in der Mathematik auflistet. Aber ein solches lineares Programmierproblem ist es bisher nicht lösbar?

algorithms polynomial-time linear-programming Krebto
quelle
Lineare Programmierprobleme scheinen mit dem Simplex-Algorithmus in Polynomzeit gelöst zu werden. Es fehlt nur der Beweis. Plus das Problem, dass es Gegenbeispiele geben könnte , aber sie scheinen sehr schwer zu finden.
gnasher729
2
@ gnasher729 Es sind Gegenbeispiele bekannt, zB der Klee-Minty-Würfel . Andererseits gibt es innere Punktalgorithmen, von denen bekannt ist, dass sie in (schwacher) Polynomzeit ablaufen.
Tavian Barnes
Dieses Papier ist verwandt: cc.gatech.edu/~vempala/papers/affine.pdf
Erel Segal-Halevi

Antworten:

12

Dieses Problem ist noch offen. Siehe zum Beispiel Wikipedia , das zwar im Allgemeinen keine verlässliche Quelle ist, aber wahrscheinlich aktualisiert wird, wenn jemals ein stark polynomieller Zeitalgorithmus gefunden wird.

Yuval Filmus
quelle