I found this in my simplex code notes. I don't know what Lemke-Howson is so I doubt I read or understood it.

Y. Disser and M. Skutella (2013)

In defense of the Simplex Algorithmâ€™s worst-case behaviorâ‹†

http://arxiv.org/abs/1311.5935

These papers show that the Lemke-Howson can actually solve PSPACE-complete problems (!), and the Simplex algorithm can solve NP-hard problems, respectively (with the solution in the case of the Simplex algorithm encoded in the computation trace, obviously not by the LP solution, which can be found in polynomial time). These results highlight just how powerful these algorithms are, and they reinforce the importance of understanding what types of/ restrictions of inputs are important.

Y. Disser and M. Skutella (2013)

In defense of the Simplex Algorithmâ€™s worst-case behaviorâ‹†

http://arxiv.org/abs/1311.5935

These papers show that the Lemke-Howson can actually solve PSPACE-complete problems (!), and the Simplex algorithm can solve NP-hard problems, respectively (with the solution in the case of the Simplex algorithm encoded in the computation trace, obviously not by the LP solution, which can be found in polynomial time). These results highlight just how powerful these algorithms are, and they reinforce the importance of understanding what types of/ restrictions of inputs are important.