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?

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