3 ms·

Another example is Linear Programming - it is provably polynomial using the ellipsoid algorithm but people tend to use algorithms (such as simplex) which are no

by mitko 16y ago

Another example is Linear Programming - it is provably polynomial using the ellipsoid algorithm but people tend to use algorithms (such as simplex) which are not provably in P but run much faster in practice.

ezalor 16y ago
Logic programming (Prolog, Rebol & co) is based on these kind of ideas.
praptak 16y ago
The problem with the ellipsoid method is not speed but rather numerical stability. It would work great if we only had "real reals", i.e. reals with infinite precision.