Possible Duplicate:
Polynomial-time algorithms with huge exponent/constant
In many texts you find statements like 'The class P characterizes the problems that are efficiently solvable. Even though $n^{100}$ algorithms are in P, these don't occur in practice'.
Today I came across a $n^{120}$ algorithm for a problem where, apparently, no better algorithm is known: Recognizing Map Graphs Reference.
Then there are algorithms with huge constants like the graph minor algorithm.
Do you know of any other problems where the best known algorithm is polynomial, but terribly impractical?
