[miloshh]

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. :)

[slug]

Can you give a reference for a matrix multiplication algorithm which is O(n^1.5) ? thanks.

[miloshh]

Note that I defined n as the input size...