That's not a very good example - square matrix multiplication is O(n^1.5) (where n is the input size) and extremely fast in practice. (Though, as you say, ther

That's not a very good example - square matrix multiplication is O(n^1.5) (where n is the input size) and extremely fast in practice. (Though, as you say, there could still be an O(n) algorithm - this is not known). What I said is true even for linear programming (a P-complete problem) - it has polynomial and efficient algorithms - though the latter are actually not polynomial in the worst case. :)