> I guess this would be true even if the correct complexity was say,
O(n^2 * ln(n)
Yes you're right it would be true. We can see this by just constructing a sequence of algorithms A_i that are implementations of the putative optimal O(n^2 * ln(n)) algorithm except artificially slowed down by ever smaller polynomial overheads. But the hypothesis I'm describing above holds that no such O(n^2 * ln(n)) algorithm exists.
> Waxing theoretically, there is some integer-valued function f such that optimal matrix multiplication is...
The hypothesis I'm describing is that no optimal algorithm exists. Instead, the claim is that there is an infinite sequence of ever better algorithms (specified by ever longer sets of instructions, and with ever larger constant overheads).
Yes you're right it would be true. We can see this by just constructing a sequence of algorithms A_i that are implementations of the putative optimal O(n^2 * ln(n)) algorithm except artificially slowed down by ever smaller polynomial overheads. But the hypothesis I'm describing above holds that no such O(n^2 * ln(n)) algorithm exists.
> Waxing theoretically, there is some integer-valued function f such that optimal matrix multiplication is...
The hypothesis I'm describing is that no optimal algorithm exists. Instead, the claim is that there is an infinite sequence of ever better algorithms (specified by ever longer sets of instructions, and with ever larger constant overheads).