Klee-Minty polytope

From Glossary

Jump to: navigation, search

This is an example to show that the elementary simplex method does not have polynomial time complexity. The polytope is

\left\{ x : 
\left(\sum_{i=1}^{k-1} 2^{k-i+1} x_i \right) + x_k \le 5^k, 
<pre>               \; \mbox{ for } k = 1, 2, \ldots, n, \; x \ge 0 \right\}


\sum_{i=1}^n 2^{n-i} x_i

over this polytope shows the exponential complexity.


A measure of computer time or space to solve a problem by an algorithm as a function of the problem's dimensions. Suppose LaTeX: T(n) is the time it takes to solve an instance of the problem with dimension LaTeX: n. Then, the algorithm has (worst-case) time complexity LaTeX: K(n), if the greatest time it could take to solve an instance of the problem is LaTeX: O(K(n)). When LaTeX: K(n) is a polynomial, we say the algorithm has polynomial time complexity. The Klee-Minty polytope shows that the elementary simplex method does not have polynomial time complexity.

The average time complexity is the average (rather than worst) time of an algorithm (or class of algorithms) over some class of problems, for which some probability distribution is assumed. Absent a modifier, the complexity of an algorithm is taken to mean its worst-case time complexity.

Whereas complexity refers to the performance of an algorithm, see the notion of NP-completeness for the related meaning of problem complexity. The standard notation to describe complexity in terms of problem dimensions, say LaTeX: n, is LaTeX: O(K(n)). This ``big-O notation means the following: a function, LaTeX: f:Z^+ \rightarrow R, is LaTeX: O(K(n)) if there exists a constant, LaTeX: c, and LaTeX: N in LaTeX: Z^+, such that LaTeX: f(n) \le cK(n) for all LaTeX: n \ge N. For example, if an algorithm requires LaTeX: 5n^3 + 2n + 10 fundamental operations on a problem of size LaTeX: n, its time complexity is LaTeX: O(n^3). See the supplement on complexity for more information.

Personal tools