Constraint Calculus and Multi-typed Algebra - Polynomial Complexity

The statement on complexity requires further clarification. In the CST constraint algebra, as is common in mathematical programming, computing a linear program, i.e., minimize/maximize a linear function subject to a conjunction of linear inequalities, is a basic building block. Because of that, often complexity of mathematical programming algorithms is analyzed in terms of a number of linear programs used, and the size of the input to those linear programs. Since there are polynomial algorithms to solve a linear program (e.g., Khachiyan's or Karmarkar's), if an algorithm A requires a polynomial number of linear programs, each linear program has input of polynomial size, then the algorithm A is polynomial, provided that a polynomial (sub)algorithm is used for linear programs. In that sense, the described CST constraint algebra (but not its implementation in CCUBE!) is polynomial, i.e., provided that a polynomial algorithm is used for linear programs.

Unfortunately, the known polynomial algorithms for linear programming perform poorly in practice, typically, much worse than the exponential (in the worst case) simplex method. For that reason, the simplex method (or its variants) are very widely used, including CCUBE. Interestingly, it has been experimentally observed that the number of iterations in simplex is about linear (!) in the problem size (more specifically, linear in the number of constraints, and cubic in the number of variables). Furthermore, in theory, the average number of steps can be shown to be O(n³ m^1/(n-1)), where n is the number of variables and m is the number of constraints, under a certain natural probabilistic model. For that reason, algorithms having the complexity of a polynomial number of simplex-implemented linear programs, with polynomial input to each, can be informally called "practically" polynomial. In that sense, the CCUBE implementation of the CST algebra is "practically" polynomial.

presentation created by Victor E. Segal