Editing Simplex algorithm (section)

===Efficiency in the worst case===
The simplex method is remarkably efficient in practice and was a great improvement over earlier methods such as [[Fourier–Motzkin elimination]]. However, in 1972, [[Victor Klee|Klee]] and Minty<ref name="KleeMinty">{{cite book|title=Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, dedicated to the memory of Theodore S. Motzkin)|editor-first=Oved|editor-last=Shisha|publisher=Academic Press|location=New York-London|year=1972|mr=332165|last1=Klee|first1=Victor|author-link1=Victor Klee|last2=Minty|first2= George J.|author-link2=George J. Minty|chapter=How good is the simplex algorithm?|pages=159–175}}</ref> gave an example, the [[Klee–Minty cube]],  showing that the worst-case complexity of simplex method as formulated by Dantzig is [[exponential time]]. Since then, for almost every variation on the method, it has been shown that there is a family of linear programs for which it performs badly.  It is an open question if there is a variation with [[polynomial time]], although sub-exponential pivot rules are known.<ref>{{Citation
 | last1 = Hansen
 | first1 = Thomas
 | last2 = Zwick
 | first2 = Uri
 | title = Proceedings of the forty-seventh annual ACM symposium on Theory of Computing
 | chapter = An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
 | author2-link = Uri Zwick
 | pages = 209–218
 | year = 2015
 | doi = 10.1145/2746539.2746557
 | citeseerx = 10.1.1.697.2526
 | isbn = 9781450335362
 | s2cid = 1980659
 }}
</ref>

In 2014, it was proved{{citation-needed|date=January 2024}} that a particular variant of the simplex method is [[NP-mighty]], i.e., it can be used to solve, with polynomial overhead, any problem in NP implicitly during the algorithm's execution.  Moreover, deciding whether a given variable ever enters the basis during the algorithm's execution on a given input, and determining the number of iterations needed for solving a given problem, are both [[NP-hardness|NP-hard]] problems.<ref>{{Cite journal|last1=Disser|first1=Yann|last2=Skutella|first2=Martin|date=2018-11-01|title=The Simplex Algorithm Is NP-Mighty|journal=ACM Trans. Algorithms|volume=15|issue=1|pages=5:1–5:19|doi=10.1145/3280847|issn=1549-6325|arxiv=1311.5935|s2cid=54445546}}</ref> At about the same time it was shown that there exists an artificial pivot rule for which computing its output is [[PSPACE-complete]].<ref>{{Citation | last1 = Adler | first1 = Ilan | last2 = Christos | first2 = Papadimitriou | author2-link = Christos Papadimitriou | last3 = Rubinstein | first3 = Aviad | title = Integer Programming and Combinatorial Optimization | chapter = On Simplex Pivoting Rules and Complexity Theory | volume = 17 | pages = 13–24 | year = 2014 | arxiv = 1404.3320 | doi = 10.1007/978-3-319-07557-0_2| series = Lecture Notes in Computer Science | isbn = 978-3-319-07556-3 | s2cid = 891022 }}</ref> In 2015, this was strengthened to show that computing the output of Dantzig's pivot rule is [[PSPACE-complete]].<ref>{{Citation | last1 = Fearnly | first1 = John | last2 = Savani | first2 = Rahul | title = Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | chapter = The Complexity of the Simplex Method | pages = 201–208 | year = 2015 | arxiv = 1404.0605 | doi = 10.1145/2746539.2746558| isbn = 9781450335362 | s2cid = 2116116 }}</ref>