Complexity and computability of solutions to linear programming systems

Through key examples and constructs, exact and approximate, complexity, computability, and solution of linear programming systems are reexamined in the light of Khachian's new notion of (approximate) solution. Algorithms, basic theorems, and alternate representations are reviewed. It is shown that the Klee-Minty example has never been exponential for (exact) adjacent extreme point algorithms and that the Balinski-Gomory (exact) algorithm continues to be polynomial in cases where (approximate) ellipsoidal "centered-cutoff" algorithms (Levin, Shor, Khachian, Gacs-Lovasz) are exponential. By "model approximation," both the Klee-Minty and the new J. Clausen examples are shown to be trivial (explicitly solvable) interval programming problems. A new notion of computable (approximate) solution is proposed together with an a priori regularization for linear programming systems. New polyhedral "constraint contraction" algorithms are proposed for approximate solution and the relevance of interval programming for good starts or exact solution is brought forth. It is concluded from all this that the "imposed problem ignorance" of past complexity research is deleterious to research progress on "computability" or "efficiency of computation."