2 ms·
> I conjecture that for every j > 0 in R, a number n exists so that any two n x n matrices can be multiplied together in O(n^(2+j)) steps. Is this stated corre
by gizmo686 3y ago
> I conjecture that for every j > 0 in R, a number n exists so that any two n x n matrices can be multiplied together in O(n^(2+j)) steps.
Is this stated correctly? Because it seems almost meaningless as stated. You start with "for every j, there exists an n such that...". That would mean that for the rest of the statement, n and j are constant. So you are just saying that you can multiply constant sized matrices in constant time. Technically true, but I feel like you are trying to claim something stronger.
- JohnKemeny 3y agoIt should simply say: for any j>0 there exists an algorithm multiplying nxn matrices in time O(n^{2+j}).
- Lucasoato 3y agoYou are correct, I apologize for the confusion! :)
- hnfong 3y agoAssuming your claim is not equivalent to "matrix multiplication is in O(n^2)", then it is false assuming conventional mathematics (i.e. uncountable sets exist), because j in R is uncountable, and algorithms are countable...
- akoboldfrying 3y agoAre algorithms on a Real RAM [1] countable? That would mean that there are constants you can't express. [1] https://en.wikipedia.org/wiki/Real_RAM https://en.wikipedia.org/wiki/Real_RAM
- ernesth 3y agoYou do not need a different algorithm for each real. Just take the algorithm that proves the statement for rational p. It proves the statement for all reals bigger than p. (hence having as many algorithms as there are rational (countably many) is enough)
- hnfong 3y agoThen that’s basically saying there is a O(n^2) algorithm which I dealt with in my first sentence.