The video is misleading when it spreads the idea that "polynomial time" equals "practical," or "fast". It's nice and simple to talk like that, but I don't thi

The video is misleading when it spreads the idea that "polynomial time" equals "practical," or "fast". It's nice and simple to talk like that, but I don't think it's particularly useful or helpful. For example, there is a linear time algorithm for deciding whether two planar graphs are isomorphic (Hopcroft,Wong 1974). But the constant of the asymptotic time bound of their algorithm so large that it was not useful or practical (see end of abstract, http://dl.acm.org/citation.cfm?id=803896 http://dl.acm.org/citation.cfm?id=803896) Only in 2004 did Kukluk, Holder, Cook publish a quadratic time algorithm, "suitable for practical implementation." http://www.eecs.wsu.edu/~holder/pubs/KuklukJGAA04.pdf http://www.eecs.wsu.edu/~holder/pubs/KuklukJGAA04.pdf More such examples are listed at "Polynomial-time algorithms with huge exponent/constant," http://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant http://cstheory.stackexchange.com/questions/6660/polynomial-...