Is Complexity Theory On The Brink? « Gödel’s Lost Letter and P=NP

Is Complexity Theory On The Brink? « Gödel’s Lost Letter and P=NP: "Let me give a short history of the search for “good” pivoting rules for Simplex. The Simplex method is really a family of algorithms: at each step the algorithm essentially moves around the vertices of the polytope defined by the linear constraints. The key is the decision of where to move next: the pivot rule. In practice there are many simple rules that work extremely well; however, the complexity question is to find a rule that always works efficiently."